//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu) FUNC(printe) FUNC(printe0);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

struct ExGCDRet{
    ll gcd, a, b;
    friend ostream& operator << (ostream& out, ExGCDRet& e) {
        return out << e.gcd << '(' << e.a << ',' << e.b << ')';
    }
};
ExGCDRet exGCD(ll xx, ll yy){
    // (a2 a1) = (a1 a0)(1 1 )
    // (b2 b1) = (b1 b0)(0 -k)
	ll a0 = 1, b0 = 0, a1 = 0, b1 = 1;
	while(yy){
        auto ret = lldiv(xx, yy);
        xx = yy;
        yy = ret.rem;
		ll a2 = a0 - ret.quot * a1;
        ll b2 = b0 - ret.quot * b1;
        a0 = a1; b0 = b1;
        a1 = a2; b1 = b2;
	}
	return {xx, a0, b0};
}

map<ll, int> factorization(ll n){
    map<ll, int> fs;
    auto sq = sqrt(n);
    for(int i = 2; i <= sq; i++){
        while(n % i == 0){
            fs[i]++;
            n /= i;
        }
    }
    if(n > 1){
        fs[n]++;
    }
    return fs;
}

ll solve(ll n0, ll n){
    auto fs = factorization(n);
    vector<pair<ll, int>> fs2(fs.begin(), fs.end());
    int n2 = fs2.size();
    printde(fs2);
    ll ans = n0 & 1 ? n0 - 1 : 2 * n0 - 1;
    for(int bits = 0; bits < (1 << n2); bits++){
        ll num1 = 1, num2 = 1;
        for(int i = 0; i < n2; i++){
            for(int j = 0; j < fs2[i].second; j++){
                (bits >> i & 1 ? num1 : num2) *= fs2[i].first;
            }
        }
        auto ret = exGCD(num1, num2);
        //TODO
        ll k1 = abs(num1 * ret.a), k2 = abs(num2 * ret.b);
        if(k1 == 0 || k2 == 0){
            continue;
        }
        if(k1 > k2){
            swap(k1, k2);
            swap(num1, num2);
            swap(ret.a, ret.b);
        }
        if(k2 - k1 != 1 || k1 / num1 != abs(ret.a) || k2 / num2 != abs(ret.b)){
            printde(ret);
            printde(k1, k2, num1, num2);
            exit(1);
        }
        __int128 k3 = k1;
        k3 *= k2;
        k3 /= 2;
        if(k3 % n0){
            continue;
        }
        // __int128 k1 = num1;
        // k1 *= ret.second.first;
        // __int128 k2 = num2;
        // k2 *= ret.second.second;
        // __int128 cand = k1 < k2 ? k1 : k2;
        ll cand = k1;
        if(cand == 0){
            continue;
        }
        ans = min(ans, cand);
        printde(num1, num2, ret);
        printde(k1, k2, cand);
    }
    return ans;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n; cin >> n;
    if(n == 1){
        cout << 1 << '\n';
        return 0;
    }
    cout << min(solve(n, n), solve(n, n * 2)) << '\n';
    // for(int n = 1; n < 10000; n++){
    //     // auto ans = solve(n, n);
    //     auto ans = min(solve(n, n), solve(n, n * 2));
    //     for(ll i = 1; i < ans; i++){
    //         if(i * (i + 1) / 2 % n == 0){
    //             printde(n, ans, i);
    //             return 0;
    //         }
    //     }
    // }
}


Measured memory_bytes: 3164