#include "gondola.h"
#include<stack>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
int m2[100005];
bool exist[250005];
int res[250005], origin[100005];
const ll MOD=1e9+9;
int valid(int N, int *M)
{
int val=M[0], idx=0;
for(int i=0 ; i<N ; i++) m2[i]=M[i];
sort(m2,m2+N);
for(int i=1 ; i<N ; i++)
{
if(m2[i]==m2[i-1]) return 0;
}
for(int i=1 ; i<N ; i++)
{
if(val>M[i]) val=M[i], idx=i;
}
if(val>N) return 1;
int nxt=val;
for(int i=1 ; i<N ; i++)
{
(idx+=1)%=N;
nxt++;
if(nxt>N) nxt=1;
if(M[idx]>N) continue;
if(M[idx]!=nxt) return 0;
}
return 1;
}
void make_origin(int N, int *M)
{
int val=M[0], idx=0;
for(int i=1 ; i<N ; i++) if(val>M[i]) val=M[i], idx=i;
if(val>N)
{
for(int i=0 ; i<N ; i++) origin[i]=i+1;
return;
}
int nxt=val;
origin[idx]=nxt;
for(int i=1 ; i<N ; i++)
{
(idx+=1)%=N;
nxt++;
if(nxt>N) nxt=1;
origin[idx]=nxt;
}
}
int replacement(int N, int *M, int *ret)
{
make_origin(N,M);
priority_queue<P> PQ;
for(int i=0 ; i<N ; i++)
{
exist[M[i]]=true;
PQ.push(P(M[i],i));
}
stack<int> S;
int idx=PQ.top().first;
while(PQ.top().first!=N)
{
int pval, tsec=PQ.top().second;
while(exist[idx]) idx--;
pval=idx;
if(idx<=N) pval=origin[tsec];
PQ.pop();
PQ.push(P(pval,tsec));
exist[pval]=true;
S.push(pval);
}
int rcnt=0;
while(!S.empty())
{
ret[rcnt++]=S.top();
S.pop();
}
return rcnt;
}
ll get_pow(ll x, int y)
{
if(y==0) return 1;
if(y==1) return x;
ll ret=get_pow(x,y/2);
(ret*=ret)%=MOD;
if(y%2==1) (ret*=x)%=MOD;
return ret;
}
int countReplacement(int N, int *M)
{
int val=M[0], idx=0;
ll ret=0, ecnt=0;
if(!valid(N,M)) return (int)ret;
for(int i=1 ; i<N ; i++) if(val>M[i]) val=M[i], idx=i;
priority_queue<int,vector<int>,greater<int> > PQ;
if(val>N)
{
ret=N, ecnt=N;
for(int i=0 ; i<N ; i++) PQ.push(M[i]);
}
else
{
ret=1;
int nxt=val;
for(int i=1 ; i<N ; i++)
{
(idx+=1)%=N;
nxt++;
if(nxt>N) nxt=1;
if(nxt!=M[idx]) PQ.push(M[idx]), ecnt++;
}
}
val=N+1;
while(!PQ.empty())
{
int y=PQ.top()-val;
(ret*=get_pow(ecnt,y))%=MOD;
ecnt--;
val=PQ.top()+1;
PQ.pop();
}
return (int)ret;
}
