Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt
from decimal import *
import decimal
N=int(input())
getcontext().prec=30
"""
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=Decimal(1+8*a*N).sqrt()
    #print(t)
    #print(t.to_integral_value())
    n=t.to_integral_value()
    if (pow(n,Decimal(2),1+8*a*N)==0)and(int(t)%2==1):
        print((int(t)-1)//2)
        break
    a=a+1


Fixed submission:
from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import *
from decimal import *
N=int(input())
getcontext().prec=30
"""
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=Decimal(1+8*a*N).sqrt()
    #print(t)
    #print(t.to_integral_value())
    n=t.to_integral_value()
    if ((n*n)%(1+8*a*N)==0)and(int(t)%2==1):
        print((int(t)-1)//2)
        break
    a=a+1


Fixed submission:
from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import *
N=int(input())
"""
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=sqrt(1+8*a*N)
    if (pow(int(sqrt(1+8*a*N)),2)==1+8*a*N)and(int(t)%2==1):
        print((-1+int(t))//2)
        break
    a=a+1


Fixed submission:
from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)