#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}


// 2^127 = 170141183460469231731687303715884105728 ~ 10^38
using int128=__int128;
 
ostream &operator<<(ostream &os,const __int128 n){
    if(n==0){
        os<<0;
        return os;
    }
    __int128 num=n;
    bool neg=false;
    if(num<0)neg=true,num=-num;
    string res="";
    while(num>0){
        res.push_back('0'+num%10);
        num/=10;
    }
    if(neg) res.push_back('-');
    reverse(begin(res),end(res));
    os<<res;
    return os;
}
 
istream &operator>>(istream &is,__int128 &n){
    string s;
    is>>s;
    int idx=0;
    bool neg=false;
    if(s[0]=='-')neg=true,idx++;
    n=0;
    for(;idx<(int)s.size();idx++){
        n=10*n+s[idx]-'0';
    }
    if(neg) n=-n;
    return is;
}
 
__int128 abs128(__int128 x){
    return x<0?-x:x;
}
 
__int128 gcd128(__int128 a,__int128 b){
    if(a==0) return b;
    if(b==0) return a;
    return b>0?gcd128(b,a%b):a;
}
 
vector<int128> divisor(int128 n) {
    vector<int128> ret;
    for(int128 i=1; i*i<=n; i++) {
        if(n%i==0) {
            ret.push_back(i);
            if(n / i != i) ret.push_back(n/i);
        }
    }
    return ret;
}


void naive(int128 n){
    for(int128 i=1;;i++){
        if((i*(i+1)/2)%n==0){
            cout<<i<<endl;
            return ;
        }
    }
    cout<<"NOT YET"<<endl;
    return ;
}

int128 extgcd(int128 a, int128 b, int128& x, int128& y) {
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int128 d=extgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}


signed main(){
    int128 n;cin>>n;
    if(n==1){
        cout<<1<<endl;
        return 0;
    }
    // naive(n);

    // 2*n*t=k*(k+1)
    n*=2;
    auto d=divisor(n);


    int128 res=LINF;
    for(auto x:d){
        auto y=n/x;
        if(gcd128(x,y)!=1) continue;



        // minimize a*b (=t)
        // ax=by+1
        {
            int128 adash,bdash;
            extgcd(x,-y,adash,bdash);// ax-by=1

            // a = adash + y * u
            // b = bdash + x * u

            int128 minu=-LINF;
            {
                if(adash<0){
                    auto ab=abs128(adash);
                    chmax(minu,(ab+y-1)/y);
                }else{
                    chmax(minu,adash/y);
                }
                if(bdash<0){
                    auto bb=abs128(bdash);
                    chmax(minu,(bb+x-1)/x);
                }else{
                    chmax(minu,bdash/x);
                }
            }
            int128 a=adash+y*minu;
            int128 b=bdash+x*minu;
            if(a==0 or b==0){
                a+=y;b+=x;
            }
            chmin(res,a*x);
        }   
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 3840