Trong giải cờ vua của CLB H3.2 mở rộng dành cho K13-K19, có tất cả ~n~ đấu thủ tham gia, thể thức là đấu loại trực tiếp, nghĩa là thí sinh thua sẽ bị loại ngay (giả sử không có trận hòa xảy ra). Ban tổ chức Luna quy định khá lạ rằng: 2 thí sinh chỉ thi đấu được với nhau nếu chênh lệch số trận thắng của họ không quá 1. Tất nhiên với luật này, BTC phải tổ chức giải đấu rất cẩn thận, vì có thể xảy ra tình huống đánh đến một lúc nào đó thì không thể đánh tiếp (do các thí sinh có số trận lệch nhau nhiều hơn 1). Bây giờ giả sử rằng BTC đã sắp xếp giải đấu diễn ra tốt đẹp và cuối cùng, còn lại đúng 1 thí sinh ~X~ đạt giải vô địch, tất cả thí sinh khác đều đã bị loại. Sau khi điều tra thì biết rằng hóa ra ~X~ chính là một quốc tế đại sư ẩn danh của CLB, đẹp trai mà không mê gái, chỉ lo chuyên tâm tu luyện cờ suốt ngày đêm. Câu chuyện về ~X~ còn khá dài dòng nhưng bây giờ BTC Luna có thắc mắc rằng thí sinh ~X~ đó đã thắng được nhiều nhất bao nhiêu trận? Bạn hãy giúp BTC với nhé.

Input

Một số nguyên dương duy nhất ~n~ với ~1 \le n \le 10^{18}.~

Output

Đáp số của bài toán.

Sample input 1

3

Sample output 1

2

Sample input 2

8

Sample output 2

4

Sample input 3

16

Sample output 3

5

Sample input 4

32

Sample output 4

6

Giải thích: trong VD1, ta cho thí sinh 1-2 đấu nhau và 1 thắng, khi đó thí sinh 3 chưa đấu trận nào thì vẫn đánh được với 1 và giả sử thua 1, số trận thắng nhiều nhất của thí sinh 1 sẽ là 2 (các kịch bản khác có thể cho số trận thắng ít hơn 2). Các VD khác làm tương tự.