//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;
#define int ll
using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) (x) * (x)
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ld, ld> pld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define asd(n) rep(i, 0, n)
#define jkl(n) rep(j, 0, n)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define prev asasdasd
#define next aasdasda
#define left asdasdasdasd
#define right asnabsdkasdl
#define rank asdasdknlasd
#define move asdasdas

namespace IO {

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a);

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a);

    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
        return out;
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

pii ext_gcd(int a, int b) {
    if (b == 0) {
        return {1, 0};
    }
    pii cur = ext_gcd(b, a % b);
    return {cur.second, cur.first - (a/b) * cur.second};
}
int gcd(int a, int b) {
    return (b == 0?a:gcd(b, a % b));
}

pii diof(int a,int b, int c) {
    int d = gcd(a, b);
    if (c % d != 0) {
        return {0, 0};
    }
    pii res = ext_gcd(a, b);
    res.first = res.first * (c/d)% (b/d);
    if (res.first < 0)res.first += b/d;
    res.second = (c - a * res.first) / b;
    return res;
}
void solve() {
    int n;
    cin >> n;
    n *= 2;
    if (n == 2) {
        put(1);
        return;
    }
    int ans = n;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            int j = n / i;
            pii c = diof(i, j, 1);
            if (c.first == 0 || c.second == 0)continue;
            chkmin(ans, max(c.first * i, c.second * j) - 1);
            int t = (-c.second + i - 1) / i;
            c.first -= j * t;
            c.second += i * t;
            if (c.first == 0 || c.second == 0)continue;
            chkmin(ans, max(c.first * i, c.second * j) - 1);
        }
    }
    put(ans);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(30);
//    freopen("input.txt", "r", stdin);
    int q = 1;
//    cin >> q;

    while (q--) solve();
}


Measured memory_bytes: 3204