import java.math.BigInteger;
import java.util.Scanner;

public class lowest_higher{
    private static BigInteger zero = BigInteger.ZERO;
    private static BigInteger one = BigInteger.ONE;
    private static BigInteger two = BigInteger.valueOf(2);
    private static BigInteger three = BigInteger.valueOf(3);
    private static BigInteger four = BigInteger.valueOf(4);
    private static BigInteger five = BigInteger.valueOf(5);
    private static BigInteger six = BigInteger.valueOf(6);
    private static BigInteger eight = BigInteger.valueOf(8);
    private static int count = 0;
    private static boolean decided = false;
    private static BigInteger landed = zero;
    private static BigInteger a = zero;
    private static BigInteger b;
    private static BigInteger c;
    private static BigInteger upper_bound_real;
    private static BigInteger i;
    private static BigInteger d;
    private static BigInteger n;
    private static BigInteger o;
    private static BigInteger x;
    private static BigInteger j;
    private static BigInteger test = zero;
    private static BigInteger old_middle = zero;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str;
        System.out.print("c=");
        str = input.nextLine();
        c = new BigInteger(str);
        d = sqrt(c);
        upper_bound_real = c.subtract(eight).divide(six).add(three);
        BigInteger mid_index = upper_bound_real.divide(two);
	i = binary_search(mid_index, upper_bound_real, zero);

	System.out.println("The lowest possible i that doesn't create an imaginary number is " + lowest_higher);
	o = i.pow(2);
	BigInteger jSquared = o.subtract(c);
	x = (sqrt(jSquared)).subtract(n);
	j = x.add(n);
	a = i.subtract(j);
	b = i.add(j);
	test = a.multiply(b);
	if(test.equals(c)){
	    System.out.println("It is the correct i: c = " + c + ", test = " + test);
	} else {
	    System.out.println("It is an incorrect i: c = " + c + ", test = " + test);
	}
    }

    public static BigInteger binary_search(BigInteger mid_index, BigInteger upper_bound, BigInteger lower_bound) {
        while (!(decided)) {
            System.out.println("Upper = " + upper_bound +
			       ", middle = " + mid_index +
			       ", lower = " + lower_bound);

	    //The middle either produces an imaginary number or doesn't.
	    //If it does, it's too small.
	    //If it doesn't, it's too big.
	    n = mid_index.subtract(d);
	    o = mid_index.pow(2);
	    old_middle = mid_index;
	    if(lessThan(o, c)){
		lower_bound = mid_index.add(one);
		mid_index = lower_bound.add((upper_bound.subtract(lower_bound)).divide(two));
	    } else {
		upper_bound = mid_index.subtract(one);
		mid_index = lower_bound.add((upper_bound.subtract(lower_bound)).divide(two));
	    }
	    if(upper_bound.equals(lower_bound)){
		landed = upper_bound;
		decided = true;
	    }
	    //if lower_bound > upper_bound, landed = old middle
	    if(greaterThan(lower_bound, upper_bound)){
		landed = old_middle;
		decided = true;
	    }
	}

        //middle is either the highest lower (creates an imaginary number) or the lowest higher (doesn't)
	//for the sake of this program we want the lowest higher, because it could be the i for our c
	if(lessThan(landed.pow(2), c)){
	    return landed.add(one);
	}
	return landed;
    }

    public static BigInteger sqrt(BigInteger i) {
        BigInteger zero = BigInteger.ZERO;
        BigInteger one = BigInteger.ONE;
        BigInteger n = zero;
        BigInteger p = zero;

        if (i.equals(zero)) {
            return zero;
        } else if (i.equals(one)) {
            return one;
        }

        BigInteger high = i.shiftRight(1);
        BigInteger low = zero;

        //high > low + 1
        while (greaterThan(high, low.add(one))) {
            //n = (high + low) >> 1;
            n = (high.add(low)).shiftRight(1);
            p = n.multiply(n);
            int result = i.compareTo(p);
            if (result == -1) {
                high = n;
            } else if (result == 1) {
                low = n;
            } else {
                break;
            }
        }

        if (i.equals(p)) {
            return n;
        } else {
            return low;
        }
    }

    public static boolean greaterThan(BigInteger i, BigInteger i2) {
        int result = i.compareTo(i2);

        return result > 0;
    }

    public static boolean lessThan(BigInteger i, BigInteger i2) {
        int result = i.compareTo(i2);

        return result < 0;
    }
}