import sys, time
from math import isqrt

# ---- FINAL VERSION to ship ----
def T(k): return k*(k+1)//2

def phase2_feasible(k, l, n):
    """O(1)-ish replacement: is (S2-n)/2 a subset sum of {k+1,...,l}?"""
    S2 = T(l) - T(k)
    if (S2 - n) % 2 != 0:
        return False
    target = (S2 - n) // 2
    if target < 0 or target > S2:
        return False
    if target == 0 or target == S2:
        return True
    a, b, m = k + 1, l, l - k
    # j-subset sums fill exactly [j*a + C(j,2), j*b - C(j,2)]; find the only
    # candidate layer j and test membership.
    c = 2*a - 1
    j = (isqrt(c*c + 8*target) - c) // 2
    Lo = lambda j: j*a + j*(j-1)//2
    while j > 0 and Lo(j) > target: j -= 1
    while j < m and Lo(j+1) <= target: j += 1
    j = max(0, min(j, m))
    return Lo(j) <= target <= j*b - j*(j-1)//2

def f(n, k_pad=15, l_pad=25, _hard_cap=2_000_000):
    n = abs(n)
    if n == 0: return 0
    k0 = isqrt(2*n)
    while T(k0) < n: k0 += 1
    l0 = max(2*isqrt(n), k0)
    l, kp, lp = l0, k_pad, l_pad
    while l < l0 + _hard_cap:
        for ll in range(l, l + lp):
            for k in range(k0, min(ll, k0 + kp) + 1):
                if (T(k) - n) % 2: continue
                if T(ll) - T(k) < n: continue
                if phase2_feasible(k, ll, n):
                    return ll
        l += lp; kp *= 2; lp *= 2   # widen the net if (never observed to trigger)
    raise RuntimeError("unexpected: no solution in expanded range")

# 1) reproduce given examples
print("Given examples check:")
for n,expected in [(1,3),(2,7),(3,3),(4,4),(5,8)]:
    got = f(n)
    print(f"  f({n}) = {got}  (expected {expected})  {'OK' if got==expected else 'FAIL'}")

# 2) cross-check vs the ORIGINAL slow code on n=1..3000
def phase2_feasible_orig(k, l, n):
    S2 = T(l) - T(k)
    if (S2 - n) % 2 != 0: return False
    T2p = (S2 - n) // 2
    if T2p < 0: return False
    if T2p == 0: return True
    a = k + 1
    if T2p < a: return False
    reachable = {0}
    for i in range(a, l + 1):
        reachable |= {x + i for x in reachable if x + i <= T2p}
    return T2p in reachable

def travel_orig(n):
    n = abs(n)
    k_min = isqrt(2*n)
    l_min = 2 * isqrt(n)
    while T(k_min) < n: k_min += 1
    for l in range(l_min, l_min+10):
        for k in range(k_min, k_min + 10):
            if (T(k) - n) % 2 != 0: continue
            if phase2_feasible_orig(k, l, n):
                return l
    return None

mism = 0
t0=time.time()
for n in range(1, 3000):
    a, b = f(n), travel_orig(n)
    if a != b:
        mism += 1
        print("MISMATCH", n, a, b)
print(f"n=1..2999 vs original code: {mism} mismatches, {time.time()-t0:.2f}s")

# 3) huge n timing
print("\nHuge-n timing:")
for n in [10**6, 10**32, 10**100, 10**1000]:
    t0=time.time()
    res = f(n)
    print(f"  n~10^{len(str(n))-1}: f(n) has {len(str(res))} digits, computed in {(time.time()-t0)*1000:.3f} ms")