#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <limits>
#include <list>
#include <numeric>
#include <queue>
#include <stack>
#include <utility>
#include <array>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;
typedef long long ll;
#define dump(x) cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl;
// vector出力
template < typename T >
ostream& operator<<(ostream& os, vector< T >& v) {
    os << "{";
    for (int i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i < v.size() - 1 ? ", " : "");
    }
    os << "}";
    return os;
}
// pair出力
template < typename T, typename U >
ostream& operator<<(ostream& os, pair< T, U >& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// map出力
template < typename T, typename U >
ostream& operator<<(ostream& os, map< T, U >& map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template < typename T >
ostream& operator<<(ostream& os, set< T >& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#pragma endregion

/////////////////////////////////////////

// 中国剰余定理
// x = r_i mod m_i (i=0~n-1) となる 
// x = y mod lcm(m) を (y,lcm(m)) で返す
// ないなら(0,0)
// O(nlog(lcm(m)))
constexpr long long _safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

constexpr std::pair<long long, long long> _inv_gcd(long long a, long long b) {
    a = _safe_mod(a, b);
    if (a == 0) return {b, 0};

    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

std::pair<long long, long long> crt(const std::vector<long long>& r, const std::vector<long long>& m) {
    assert(r.size() == m.size());
    int n = int(r.size());
    // Contracts: 0 <= r0 < m0
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        long long r1 = _safe_mod(r[i], m[i]), m1 = m[i];
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        long long g, im;
        std::tie(g, im) = _inv_gcd(m0, m1);

        long long u1 = (m1 / g);
        if ((r1 - r0) % g) return {0, 0};

        long long x = (r1 - r0) / g % u1 * im % u1;

        r0 += x * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

// enum_div 約数列挙O(√N)
// 順番はバラバラ
template<typename T>
vector<pair<T,T>> enum_div(T n) {
    vector<pair<T,T>> ret;
    for (T i = 1; i * i < n; ++i)
    {
        if (n % i == 0)
        {
            ret.push_back({i,n/i});
            if (i != 1) ret.push_back({n/i,i});
        }
    }
    return ret;
}

int main() {
    ll n;cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    auto v = enum_div(2*n);
    constexpr long long LLINF = 1e18 + 1;
    ll ans = LLINF;
    for (auto p : v) {
        auto q = crt({0,p.second-1},{p.first,p.second});
        // cout << p << q << endl;
        if (q.second != 2 * n) continue;
        ans = min(ans,q.first);
    }
    cout << ans << endl;
    return 0;
}

/////////////////////////////////////////

Measured memory_bytes: 3840