int floorSqrt(int n)
{
    // int ans = sqrt(n);
    // return ans;

    int low=1;
    int high=n;
    int ans=0;
    while(low<=high){
        long long mid=(low+high)/2;
        long long val = mid*mid;
        if(val <=(long long) n){
            low=mid+1;
            ans=mid;
        }
        else{
            high=mid-1;
        }
    }
    return high;

}