Sqrt-D&C

def sqrt(x: int, l: int, r: int):
    m = (l + r) // 2
    if (m + 1) ** 2 > x and m ** 2 <= x:
        return m

    if m ** 2 < x:
        return sqrt(x, m, r)
    else:
        return sqrt(x, l , m)

def main():
    # exanple usage
    n = int(input())
    print(sqrt(n, 1, n))

main()