#include "gondola.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MOD=1e9+9;
void rot(int n,int inputSeq[])
{
int gmn=0;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<inputSeq[gmn])
gmn=i;
}
rotate(inputSeq,inputSeq+gmn,inputSeq+n);
return;
}
int valid(int n,int inputSeq[])
{
set<int> vis;
for(int i=0;i<n;i++)
{
if(vis.find(inputSeq[i])!=vis.end())
return 0;
vis.insert(inputSeq[i]);
}
rot(n,inputSeq);
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n && inputSeq[i]!=inputSeq[0]+i)
return 0;
}
return 1;
}
bool comp_se(pair<int,int> a,pair<int,int> b)
{
if(a.se==b.se)
return a.fi<b.fi;
return a.se<b.se;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
int l=0;
vector<pair<int,int>> ch;
rot(n,gondolaSeq);
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]>n)
ch.emplace_back((gondolaSeq[0]+i-1)%n+1,gondolaSeq[i]);
}
sort(ch.begin(),ch.end(),comp_se);
int nxt=n+1;
for(auto v:ch)
{
replacementSeq[l++]=v.fi;
while(nxt<v.se)
replacementSeq[l++]=nxt++;
nxt++;
}
return l;
}
int qp(int x,int y)
{
if(y==0)
return 1;
long long pp=qp(x,y/2);
pp=(pp*pp)%MOD;
if(y%2==1)
return (pp*x)%MOD;
return pp;
}
int countReplacement(int n,int inputSeq[])
{
if(valid(n,inputSeq)==0)
return 0;
long long ans=1;
vector<int> ch;
for(int i=0;i<n;i++)
{
if(inputSeq[i]>n)
ch.emplace_back(inputSeq[i]);
}
sort(ch.begin(),ch.end());
int lst=n,free=ch.size();
for(auto v:ch)
{
ans=(ans*qp(free,v-lst-1))%MOD;
lst=v;
free--;
}
return ans;
}
