#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=101000;
typedef double db;
db dp[N],ldp[N];
int p1[N],p2[N];
int sp[N],lsp[N],n;
db calc(int x,int y) {
db val=dp[x]+dp[y]+min(x,y)+x+y;
db bp=0;
db pr=1;
rep(i,1,x+1) {
pr=pr*(x+1-i)/(x+y+1-i);
bp+=pr;
if (pr<1e-10) break;
}
pr=1;
rep(i,1,y+1) {
pr=pr*(y+1-i)/(x+y+1-i);
bp+=pr;
if (pr<1e-10) break;
}
val-=bp;
// printf("%.10f\n",bp);
return val;
}
db lcalc(int x,int y) {
db val=ldp[x]+dp[y]+min(x,y)+x+y-p1[x];
db bp=0;
db pr=1;
rep(i,1,x+1) {
pr=pr*(x+1-i)/(x+y+1-i);
bp+=pr;
if (pr<1e-10) break;
}
pr=1;
rep(i,1,y+1) {
pr=pr*(y+1-i)/(x+y+1-i);
bp+=pr;
if (pr<1e-10) break;
}
val-=bp;
// printf("%d %d %d\n",x,y,p1[x]);
return val;
}
int pans=0;
int cnt[N],perm[N],ins[N],rd[N];
int totQ;
int Query(int u) {
++totQ;
if (ins[u]) {
cnt[perm[u]]--;
if (cnt[perm[u]]==0) pans--;
} else {
cnt[perm[u]]++;
if (cnt[perm[u]]==1) pans++;
}
ins[u]^=1;
return pans;
}
int pre,pins[N];
VI x,y;
struct RNG {
int operator() (int n) {
return rnd(n);
}
};
void query(int u) {
pre=Query(rd[u]);
}
bool inside(int u) {
int cur=pre;
pre=Query(rd[u]);
return pre==cur;
}
void Answer(int u,int v) {
assert(perm[u]==perm[v]);
}
void prec(int n) {
rep(i,0,2*n) perm[i+1]=i/2;
random_shuffle(perm+1,perm+2*n+1);
}
int bp=0;
void gao(int l,int r,VI c,bool f) {
int n=r-l+1,md=0;
if (n==1) { Answer(rd[x[l]],rd[c[0]]); return; }
if (f) {
md=r-sp[n];
rep(i,md+1,r+1) query(x[i]);
} else {
md=l+sp[n]-1;
rep(i,l,md+1) query(x[i]);
}
VI fl,fr;
random_shuffle(all(c),RNG());
rep(i,0,SZ(c)) {
if (SZ(fl)==md-l+1) fr.pb(c[i]);
else if (SZ(fr)==r-md) fl.pb(c[i]);
else if (l==0&&pins[c[i]]<=md) fl.pb(c[i]);
else if (inside(c[i])) fl.pb(c[i]);
else fr.pb(c[i]);
}
gao(l,md,fl,1);
gao(md+1,r,fr,0);
}
void Solve(int nn) {
n=nn;
prec(n);
rep(i,1,2*n+1) rd[i]=i;
random_shuffle(rd+1,rd+2*n+1,RNG());
rep(i,1,2*n+1) {
if (inside(i)) {
pins[i]=SZ(x)-1;
p1[SZ(x)]++;
p2[SZ(x)]+=1./SZ(x);
y.pb(i);
} else {
x.pb(i);
}
}
rep(i,1,n+1) p1[i]+=p1[i-1];
per(i,1,n+1) p2[i]+=p2[i+1];
rep(i,2,n+1) {
dp[i]=1e9;
int pl=max(1,sp[i-1]);
db fval=calc(pl,i-pl);
while (pl<i/2) {
db gval=calc(pl+1,i-pl-1);
if (fval>gval) fval=gval,++pl;
else break;
}
dp[i]=fval; sp[i]=pl;
}
gao(0,n-1,y,1);
printf("%d\n",totQ);
}
int main() {
Solve(44000);
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcmVwKGksYSxuKSBmb3IgKGludCBpPWE7aTxuO2krKykKI2RlZmluZSBwZXIoaSxhLG4pIGZvciAoaW50IGk9bi0xO2k+PWE7aS0tKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIFNaKHgpICgoaW50KSh4KS5zaXplKCkpCnR5cGVkZWYgdmVjdG9yPGludD4gVkk7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gUElJOwptdDE5OTM3IG1yYW5kKHJhbmRvbV9kZXZpY2V7fSgpKTsgCmNvbnN0IGxsIG1vZD0xMDAwMDAwMDA3OwppbnQgcm5kKGludCB4KSB7IHJldHVybiBtcmFuZCgpICUgeDt9CmxsIHBvd21vZChsbCBhLGxsIGIpIHtsbCByZXM9MTthJT1tb2Q7IGFzc2VydChiPj0wKTsgZm9yKDtiO2I+Pj0xKXtpZihiJjEpcmVzPXJlcyphJW1vZDthPWEqYSVtb2Q7fXJldHVybiByZXM7fQpsbCBnY2QobGwgYSxsbCBiKSB7IHJldHVybiBiP2djZChiLGElYik6YTt9Ci8vIGhlYWQKCgpjb25zdCBpbnQgTj0xMDEwMDA7CnR5cGVkZWYgZG91YmxlIGRiOwoKZGIgZHBbTl0sbGRwW05dOwppbnQgcDFbTl0scDJbTl07CmludCBzcFtOXSxsc3BbTl0sbjsKCmRiIGNhbGMoaW50IHgsaW50IHkpIHsKCWRiIHZhbD1kcFt4XStkcFt5XSttaW4oeCx5KSt4K3k7CglkYiBicD0wOwoJZGIgcHI9MTsKCXJlcChpLDEseCsxKSB7CgkJcHI9cHIqKHgrMS1pKS8oeCt5KzEtaSk7CgkJYnArPXByOwoJCWlmIChwcjwxZS0xMCkgYnJlYWs7Cgl9Cglwcj0xOwoJcmVwKGksMSx5KzEpIHsKCQlwcj1wciooeSsxLWkpLyh4K3krMS1pKTsKCQlicCs9cHI7CgkJaWYgKHByPDFlLTEwKSBicmVhazsKCX0KCXZhbC09YnA7Ci8vCXByaW50ZigiJS4xMGZcbiIsYnApOwoJcmV0dXJuIHZhbDsKfQoKZGIgbGNhbGMoaW50IHgsaW50IHkpIHsKCWRiIHZhbD1sZHBbeF0rZHBbeV0rbWluKHgseSkreCt5LXAxW3hdOwoJZGIgYnA9MDsKCWRiIHByPTE7CglyZXAoaSwxLHgrMSkgewoJCXByPXByKih4KzEtaSkvKHgreSsxLWkpOwoJCWJwKz1wcjsKCQlpZiAocHI8MWUtMTApIGJyZWFrOwoJfQoJcHI9MTsKCXJlcChpLDEseSsxKSB7CgkJcHI9cHIqKHkrMS1pKS8oeCt5KzEtaSk7CgkJYnArPXByOwoJCWlmIChwcjwxZS0xMCkgYnJlYWs7Cgl9Cgl2YWwtPWJwOwovLwlwcmludGYoIiVkICVkICVkXG4iLHgseSxwMVt4XSk7CglyZXR1cm4gdmFsOwp9CgppbnQgcGFucz0wOwppbnQgY250W05dLHBlcm1bTl0saW5zW05dLHJkW05dOwppbnQgdG90UTsKCmludCBRdWVyeShpbnQgdSkgewoJKyt0b3RROwoJaWYgKGluc1t1XSkgewoJCWNudFtwZXJtW3VdXS0tOwoJCWlmIChjbnRbcGVybVt1XV09PTApIHBhbnMtLTsKCX0gZWxzZSB7CgkJY250W3Blcm1bdV1dKys7CgkJaWYgKGNudFtwZXJtW3VdXT09MSkgcGFucysrOwoJfQoJaW5zW3VdXj0xOwoJcmV0dXJuIHBhbnM7Cn0KCmludCBwcmUscGluc1tOXTsKVkkgeCx5OwoKc3RydWN0IFJORyB7CiAgICBpbnQgb3BlcmF0b3IoKSAoaW50IG4pIHsKICAgICAgICByZXR1cm4gcm5kKG4pOwogICAgfQp9OwoKdm9pZCBxdWVyeShpbnQgdSkgewoJcHJlPVF1ZXJ5KHJkW3VdKTsKfQoKYm9vbCBpbnNpZGUoaW50IHUpIHsKCWludCBjdXI9cHJlOwoJcHJlPVF1ZXJ5KHJkW3VdKTsKCXJldHVybiBwcmU9PWN1cjsKfQoKdm9pZCBBbnN3ZXIoaW50IHUsaW50IHYpIHsKCWFzc2VydChwZXJtW3VdPT1wZXJtW3ZdKTsKfQoKdm9pZCBwcmVjKGludCBuKSB7CglyZXAoaSwwLDIqbikgcGVybVtpKzFdPWkvMjsKCXJhbmRvbV9zaHVmZmxlKHBlcm0rMSxwZXJtKzIqbisxKTsKfQoKaW50IGJwPTA7Cgp2b2lkIGdhbyhpbnQgbCxpbnQgcixWSSBjLGJvb2wgZikgewoJaW50IG49ci1sKzEsbWQ9MDsKCWlmIChuPT0xKSB7IEFuc3dlcihyZFt4W2xdXSxyZFtjWzBdXSk7IHJldHVybjsgfQoJaWYgKGYpIHsKCQltZD1yLXNwW25dOwoJCXJlcChpLG1kKzEscisxKSBxdWVyeSh4W2ldKTsKCX0gZWxzZSB7CgkJbWQ9bCtzcFtuXS0xOwoJCXJlcChpLGwsbWQrMSkgcXVlcnkoeFtpXSk7Cgl9CglWSSBmbCxmcjsKCXJhbmRvbV9zaHVmZmxlKGFsbChjKSxSTkcoKSk7CglyZXAoaSwwLFNaKGMpKSB7CgkJaWYgKFNaKGZsKT09bWQtbCsxKSBmci5wYihjW2ldKTsKCQllbHNlIGlmIChTWihmcik9PXItbWQpIGZsLnBiKGNbaV0pOwoJCWVsc2UgaWYgKGw9PTAmJnBpbnNbY1tpXV08PW1kKSBmbC5wYihjW2ldKTsKCQllbHNlIGlmIChpbnNpZGUoY1tpXSkpIGZsLnBiKGNbaV0pOwoJCWVsc2UgZnIucGIoY1tpXSk7Cgl9CglnYW8obCxtZCxmbCwxKTsKCWdhbyhtZCsxLHIsZnIsMCk7Cn0KCnZvaWQgU29sdmUoaW50IG5uKSB7CgluPW5uOwoJcHJlYyhuKTsKCXJlcChpLDEsMipuKzEpIHJkW2ldPWk7CglyYW5kb21fc2h1ZmZsZShyZCsxLHJkKzIqbisxLFJORygpKTsKCXJlcChpLDEsMipuKzEpIHsKCQlpZiAoaW5zaWRlKGkpKSB7CgkJCXBpbnNbaV09U1ooeCktMTsKCQkJcDFbU1ooeCldKys7CgkJCXAyW1NaKHgpXSs9MS4vU1ooeCk7CgkJCXkucGIoaSk7CgkJfSBlbHNlIHsKCQkJeC5wYihpKTsKCQl9Cgl9CglyZXAoaSwxLG4rMSkgcDFbaV0rPXAxW2ktMV07CglwZXIoaSwxLG4rMSkgcDJbaV0rPXAyW2krMV07CglyZXAoaSwyLG4rMSkgewoJCWRwW2ldPTFlOTsKCQlpbnQgcGw9bWF4KDEsc3BbaS0xXSk7CgkJZGIgZnZhbD1jYWxjKHBsLGktcGwpOwoJCXdoaWxlIChwbDxpLzIpIHsKCQkJZGIgZ3ZhbD1jYWxjKHBsKzEsaS1wbC0xKTsKCQkJaWYgKGZ2YWw+Z3ZhbCkgZnZhbD1ndmFsLCsrcGw7CgkJCWVsc2UgYnJlYWs7CgkJfQoJCWRwW2ldPWZ2YWw7IHNwW2ldPXBsOwoJfQoJZ2FvKDAsbi0xLHksMSk7CglwcmludGYoIiVkXG4iLHRvdFEpOwp9CgppbnQgbWFpbigpIHsKCVNvbHZlKDQ0MDAwKTsKfQ==