Cho số ~N~, hãy tìm số tự nhiên ~M~ nhỏ nhất nhỏ hơn ~N~ sao cho chênh lệch giữa tổng các số từ ~1~ đến ~M~ với tổng các số từ ~M+1~ đến ~N~ là nhỏ nhất.

Input Specification

• Một dòng chứa số nguyên ~N~ ~(1 \le N \le 10^{12})~

Output Specification

• Một dòng chứa kết quả bài toán

Sample Input

10

Sample Output

7