Cho một số nguyên dương \(N\). Hãy tìm số nguyên không âm \(X\) lớn nhất sao cho: \(X^2 \le N\)

Yêu cầu: Không được sử dụng các hàm tính căn bậc hai có sẵn của ngôn ngữ lập trình (như sqrt() hay pow()) để tránh các sai số số thực và rèn luyện thuật toán tìm kiếm nhị phân.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 10^{18}\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là giá trị \(X\) lớn nhất thỏa mãn.

Ví dụ

Đầu vào:

10

Đầu ra:

3

Giải thích: \(3^2 = 9 \le 10\), còn \(4^2 = 16 > 10\). Do đó số nguyên lớn nhất là \(3\).