using System;

public class IntegerSquareRoot
{
    public static long IntegerSqrt(long n)
    {
        if (n < 0)
            throw new ArgumentOutOfRangeException(nameof(n), "Input must be non-negative.");
        if (n == 0 || n == 1)
            return n;

        // Initial guess using MathF.ReciprocalSqrtEstimate
        float reciprocalSqrtEstimate = MathF.ReciprocalSqrtEstimate((float)n);
        float initialGuess = 1.0f / reciprocalSqrtEstimate;

        // Refine the guess using Newton-Raphson iterations
        double guess = initialGuess;
        for (int i = 0; i < 5; i++) // 5 iterations for better precision with long
        {
            guess = (guess + n / guess) * 0.5;
        }

        // Convert the refined guess to a long
        long result = (long)guess;

        // Ensure the result is correct
        if (result * result > n)
            result--;
        return result;
    }

    public static void Main()
    {
        // Test cases
        Console.WriteLine(IntegerSqrt(0));  // Output: 0
        Console.WriteLine(IntegerSqrt(1));  // Output: 1
        Console.WriteLine(IntegerSqrt(2));  // Output: 1
        Console.WriteLine(IntegerSqrt(3));  // Output: 1
        Console.WriteLine(IntegerSqrt(4));  // Output: 2
        Console.WriteLine(IntegerSqrt(5));  // Output: 2
        Console.WriteLine(IntegerSqrt(48)); // Output: 6
        Console.WriteLine(IntegerSqrt(49)); // Output: 7
        Console.WriteLine(IntegerSqrt(9223372036854775807)); // Output: 3037000499
    }
}