n = $stdin.readline.to_i
m = Math::sqrt(2 * n).to_i

def ext_gcd(a, b)
  if b == 0
    return [a, 1, 0]
  end
  
  pg, px, py = ext_gcd(b, a % b)
  return [pg, py, px - (a / b) * py]
end

def chinese_rem(b1, m1, b2, m2)
  d, x, y = ext_gcd(m1, m2)
  if (b2 - b1) % d != 0
    return [nil, nil]
  end

  m = m1 * (m2 / d)
  t = (x * ((b2 - b1) / d)) % (m2 / d)
  r = (b1 + m1 * t) % m
  return [r, m]
end

k = []
1.step(m) do |x|
  if (2 * n) % x == 0
    y = (2 * n) / x
    kx, _ = chinese_rem(0, x, y - 1, y)
    k << kx if !kx.nil?
    kx, _ = chinese_rem(0, y, x - 1, x)
    k << kx if !kx.nil? && kx > 0
  end
end
puts k.min