#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e6;
const ll mod=1e9+9;
int arr[MAX],fin[MAX];
map<ll,ll> fre;
ll power(ll base,ll exp)
{
ll res=1;
while(exp)
{
if(exp%2)
res*=base;
base*=base;
res%=mod;
base%=mod;
exp/=2;
}
return res;
}
int valid(int n, int inputSeq[])
{
int N=n,ok=1;
for(int A=0;A<N;A++)
{
fre[inputSeq[A]]++;
if(fre[inputSeq[A]]>1)
return 0;
}
for(int A=0;A<N;A++)
{
if(inputSeq[A]<=N)
{
ok=0;
inputSeq[A]--;
for(int B=A;B>=0;B--)
{
arr[B]=inputSeq[A];
inputSeq[A]--;
if(inputSeq[A]<0)
inputSeq[A]+=N;
}
inputSeq[A]=arr[A];
for(int B=A+1;B<N;B++)
{
inputSeq[A]++;
if(inputSeq[A]>=N)
inputSeq[A]=0;
arr[B]=inputSeq[A];
}
inputSeq[A]=arr[A]+1;
break;
}
}
if(ok)
return 1;
for(int A=0;A<N;A++)
arr[A]++;
for(int A=0;A<N;A++)
{
if(inputSeq[A]<=N and arr[A]!=inputSeq[A])
return 0;
}
return 1;
}
//----------------------
/*int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
return -2;
}*/
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
vector<int> vec;
priority_queue<int> absent;
priority_queue<pii> present;
pii cur;
int N=n,mx=0,change=0,sec;
for(int A=0;A<N;A++)
arr[A]=A;
for(int A=0;A<N;A++)
{
if(gondolaSeq[A]<=N)
{
gondolaSeq[A]--;
for(int B=A;B>=0;B--)
{
arr[B]=gondolaSeq[A];
gondolaSeq[A]--;
if(gondolaSeq[A]<0)
gondolaSeq[A]+=N;
}
gondolaSeq[A]=arr[A];
for(int B=A+1;B<N;B++)
{
gondolaSeq[A]++;
if(gondolaSeq[A]>=N)
gondolaSeq[A]=0;
arr[B]=gondolaSeq[A];
}
gondolaSeq[A]=arr[A]+1;
break;
}
}
for(int A=0;A<N;A++)
arr[A]++;
for(int A=0;A<N;A++)
{
fre[gondolaSeq[A]]++;
mx=max(mx,gondolaSeq[A]);
present.push(mp(gondolaSeq[A],A));
if(arr[A]!=gondolaSeq[A])
change++;
}
for(int A=1;A<=mx;A++)
{
if(!fre[A])
absent.push(A);
}
while(!present.empty())
{
cur=present.top();
if(cur.first<=N+change)
break;
present.pop();
sec=absent.top();
present.push(mp(sec,cur.second));
absent.pop();
//cout<<cur.second<<" "<<cur.first<<" "<<sec<<"\n";
vec.pb(sec);
}
while(!present.empty())
{
cur=present.top();
present.pop();
fin[cur.second]=cur.first;
}
for(int A=0;A<N;A++)
{
if(fin[A]!=arr[A])
present.push(mp(fin[A],arr[A]));
}
while(!present.empty())
{
cur=present.top();
present.pop();
vec.pb(cur.second);
}
reverse(vec.begin(),vec.end());
// for(auto A:vec)
// cout<<A<<" ";
for(int A=0;A<vec.size();A++)
replacementSeq[A]=vec[A];
return vec.size();
}
//----------------------
//long long
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))
return 0;
sort(inputSeq,inputSeq+n);
vector<ll> vec;
for(int A=0;A<n;A++)
if(inputSeq[A]>n)
vec.push_back(inputSeq[A]);
if(vec.empty())
return 1;
sort(vec.begin(),vec.end());
ll res=1,ptr=0,cnt=vec.size();
while(ptr<n and inputSeq[ptr]<=n)
++ptr;
for(int A=0;A<vec.size()-1;A++)
{
while(ptr<n and inputSeq[ptr]<=vec[A])
++ptr,--cnt;
//cout<<ptr<<"\n";
//cout<<vec[A]<<" "<<cnt<<"\n";
if(vec[A+1]-vec[A]>1)
{
res*=power(cnt,vec[A+1]-vec[A]-1);
res%=mod;
}
}
if(vec[0]!=n+1)
{
res*=power((ll)vec.size(),(vec[0]-n-1));
res%=mod;
}
if(inputSeq[0]>n)
{
res*=(ll)n;
res%=mod;
}
return res;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int arr[]={3,4};
cout<<countReplacement(2,arr);
return 0;
}*/
