//{{{
#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; }
//}}}

pair<ll, pair<ll, ll>> exGCD(ll a, ll b){
	bool inv = false;
	if(a < b){
		swap(a, b);
		inv = true;
	}
	static vector<ll> r = {a, b}, ks;
    r.resize(2); r[0] = a; r[1] = b;
    ks.clear();
	while(b){
		ks.push_back(a / b);
		r.push_back(a = a % b);
		swap(a, b);
	}
	ll gcd = a;

	ll x = 0, y = 1, u = 1, v = -ks[0];
	for(int i = 1; i < (int)ks.size(); i++){
		ll k = ks[i];
		ll x2 = u, y2 = v,
		   u2 = x - k * u, v2 = y - k * v;
		x = x2; y = y2; u = u2; v = v2;
	}

	if(inv){
		swap(x, y);
	}
	return {gcd, {x, y}};
}

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.second.first), k2 = abs(num2 * ret.second.second);
        if(k1 == 0 || k2 == 0){
            continue;
        }
        if(k1 > k2){
            swap(k1, k2);
            swap(num1, num2);
            swap(ret.second.first, ret.second.second);
        }
        if(k2 - k1 != 1 || k1 / num1 != abs(ret.second.first) || k2 / num2 != abs(ret.second.second)){
            printde(ret.second);
            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: 3200