import java.math.*;
import java.util.Scanner;

//import static jan.Const.oneDigit;

public class Gradient2 {

    //constants
    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 BigInteger one_thousand = BigInteger.valueOf(1000);
    private static BigInteger highest_lower = zero;
    private static BigInteger c;
    private static BigInteger i_poss;
    private static BigInteger upper_bound_real = zero;
    private static BigInteger bound_change = zero;
    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 correct_i;
    private static BigInteger test = zero;

    private static boolean changed = false;

    /** An easy way to implement Math.ceil is just to add one, because integer truncation
     *  is effectively flooring the number.
     */
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str;

        System.out.println("What is your c value?");
        str = input.nextLine();
        c = new BigInteger(str);
	d = sqrt(c);

        i_poss = c.subtract(eight).divide(six).add(five);
        upper_bound_real = i_poss;

        //BigInteger mid_index = one;
	BigInteger mid_index = upper_bound_real.divide(two);

        correct_i = binary_search(mid_index, upper_bound_real, zero);
        BigInteger a = correct_i.subtract(j);
        BigInteger b = correct_i.add(j);
        System.out.println("For c = " + c + ", i = " + i);
        System.out.println("For c = " + c + ", a = " + a + " and b = " + b);
    }

    public static BigInteger binary_search(BigInteger mid_index,
                                     BigInteger upper_bound,
                                     BigInteger lower_bound){
        while (!test.equals(c)) {
            if (lessThan(upper_bound, lower_bound) || (((upper_bound.subtract(mid_index).equals(1)) && (mid_index.subtract(lower_bound).equals(1))))) {
		System.out.println("It runs here");
                lower_bound = upper_bound.add(three);
                upper_bound = upper_bound.subtract(four);
		if(lessThan(c, one_thousand)){
		    BigInteger temp = upper_bound;
		    upper_bound = lower_bound;
		    lower_bound = temp;
		}
            }

            System.out.println("Upper = " + upper_bound +
                    ", middle = " + mid_index +
                    ", lower = " + lower_bound);

            changed = false;
            i = mid_index;
            n = i.subtract(d);
	    o = i.multiply(i);

            if (lessThan(o, c)) {
                //then it needs to check everywhere above this point
		highest_lower = mid_index;
                lower_bound = mid_index.add(one);
                mid_index = lower_bound.add((upper_bound.subtract(lower_bound)).divide(two));
                changed = true;
            }

            x = (sqrt(o.subtract(c))).subtract(n);
            j = x.add(n);
            test = (i.subtract(j)).multiply(i.add(j));

            if (!test.equals(c)) {
                //then it needs to check everywhere below this point

                if (!(changed)) {
                    upper_bound = mid_index;
                    mid_index = upper_bound.subtract((upper_bound.subtract(lower_bound)).divide(two));

                    if (mid_index.equals(upper_bound)){
                        bound_change =  bound_change.add(one);
                        mid_index = upper_bound_real.subtract(bound_change);
                        upper_bound = upper_bound_real;
                    }
                }
            } else {
                return i;
            }
        }
        return i;
    }

    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;
    }

    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;
        }

        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;
        }
    }

}