Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,0,1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b//s
        return (s, m0)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

print(ans)

Fixed submission:
N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,0,1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b//s
        return (s, m0)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
if N==1:
    print(1)
    exit()

f = N if N%2 else 2*N
from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

fac = factorize(f)
step = len(fac)
for k,v in fac.items():
    step = max(step, k**v)

for m in range(step, 2*N, step):
    if (m*(m-1)//2) % N == 0:
        print(m-1)
        exit()
    if (m*(m+1)//2) % N == 0:
        print(m)
        exit()

print(N*2-1)

Fixed submission:
N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,0,1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b//s
        return (s, m0)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

print(ans)