#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int valid(int n, int inputSeq[])
{
lli p=-1;
for(lli i=0;i<n;++i)
{
if(inputSeq[i]<=n)
{
p=i;
break;
}
}
lli ch=0,v=inputSeq[p]-1;
if(v==0)
v=n;
for(lli i=p-1;i>=0;--i)
{
if(v==0)
v=n;
if(inputSeq[i]<=n&&inputSeq[i]!=v)
{
ch=1;
break;
}
v--;
}
v=inputSeq[p]+1;
if(v==n+1)
v=1;
for(lli i=p+1;i<n;++i)
{
if(v==n+1)
v=1;
if(inputSeq[i]<=n&&inputSeq[i]!=v)
{
ch=1;
break;
}
v++;
}
sort(inputSeq,inputSeq+n);
for(int i=1;i<n;++i)
{
if(inputSeq[i]==inputSeq[i-1])
ch=1;
}
return(!ch);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
lli p=-1;
lli x=0,v=n+1,val;
lli varr[n],val1=1;
for(lli i=0;i<n;++i)
{
if(gondolaSeq[i]<=n)
{
p=i;
break;
}
}
vector<ii> v1;
if(p!=-1)
{
val1=gondolaSeq[p]-1;
varr[p]=gondolaSeq[p];
for(lli i=p-1;i>=0;--i)
{
if(val1==0)
val1=n;
varr[i]=val1;
val1--;
}
val1=gondolaSeq[p]+1;
for(lli i=p+1;i<n;++i)
{
if(val1>n)
val1=1;
varr[i]=val1;
val1++;
}
}
for(lli i=0;i<n;++i)
{
if(p==-1)
val=i+1;
else
{
val=varr[i];
}
if(gondolaSeq[i]>n)
v1.pb(mp(gondolaSeq[i],val));
}
sort(all(v1));
for(lli i=0;i<v1.size();++i)
{
replacementSeq[x]=v1[i].S;
x++;
while(v<v1[i].F)
{
replacementSeq[x]=v;
x++;
v++;
}
v++;
}
return(x);
}
lli tel(lli p,lli n)
{
lli b=0,ans=1,a=n;
while((1LL<<b)<=p)
{
if(bit(p,b))
ans=(ans*a)%1000000009;
a=(a*a)%1000000009;
b++;
}
return(ans);
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))
return(0);
lli co=0,ans=1,l=n;
for(lli i=0;i<n;++i)
{
if(inputSeq[i]>n)
co++;
}
sort(inputSeq,inputSeq+n);
for(lli i=0;i<n;++i)
{
if(inputSeq[i]<=n)
continue;
if(co==n)
ans=(ans*tel(inputSeq[i]-l,co))%1000000009;
else
ans=(ans*tel(inputSeq[i]-l-1,co))%1000000009;
l=inputSeq[i];
co--;
}
return(ans);
}
