#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
//int gondolaSequence[100001];
//int replacementSequence[250001];
long long MOD=(long long)1e9+9ll;
long long stepen(long long x,long long y){
long long ans=1ll;
if(y==0ll)return 1;
long long tren=x;
for(int i=0;i<=30;i++){
if((1ll<<i)&y)ans=(ans*tren)%MOD;
tren=(tren*tren)%MOD;
}
return ans;
}
int valid(int n, int inputSeq[])
{
map<int,int> cnt;
for(int i=0;i<n;i++)cnt[inputSeq[i]-1]++;
bool ok=true;
for(auto a:cnt){
if (a.second>=2)ok=false;
}
int prvi=-1;
for(auto a:cnt){
if(a.second==1){
prvi=a.first;
break;
}
}
if(prvi<n){
int id=-1;
for(int i=0;i<n;i++)if(inputSeq[i]-1==prvi)id=i;
for(int i=0;i<n;i++){
if(inputSeq[id]-1<n){
if(inputSeq[id]-1!=prvi)ok=false;
}
id++;
prvi++;
id%=n;
prvi%=n;
}
}
if(ok)return 1;
return 0;
}
int replacement(int n, int inputSeq[], int rSeq[])
{
vector<int> cnt(250000);
for(int i=0;i<n;i++)cnt[inputSeq[i]-1]++;
//bool ok=true;
//for(int i=0;i<250000;i++){
//if (cnt[i]>=2)ok=false;
//}
int prvi=-1;
for(int i=0;i<250000;i++){
if(cnt[i]==1){
prvi=i;
break;
}
}
vector<pair<int,int>> v;
int id=-1;
for(int i=0;i<n;i++)if(inputSeq[i]-1==prvi)id=i;
prvi%=n;
for(int i=0;i<n;i++){
//cout<<inputSeq[id]<<' '<<prvi+1<<endl;
if(inputSeq[id]-1>=n){
v.push_back(make_pair(inputSeq[id],prvi+1));
}
id++;
prvi++;
id%=n;
prvi%=n;
}
//cout<<endl;
sort(v.begin(),v.end());
vector<int> ans;
if(v.size()==0)return 0;
int br=n+1;
int idx=0;
//for(int i=0;i<v.size();i++)cout<<v[i].first<<' '<<v[i].second<<endl;
while(idx<v.size()){
ans.push_back(v[idx].second);
v[idx].second=br;
if(br==v[idx].first)idx++;
br++;
}
int l=ans.size();
for(int i=0;i<l;i++)rSeq[i]=ans[i];
return l;
}
int countReplacement(int n, int inputSeq[])
{
//cout<<stepen(3,5)<<endl;
if(valid(n,inputSeq)==0)return 0;
vector<long long> v;
v.push_back(n);
for(int i=0;i<n;i++){
if(inputSeq[i]>n)v.push_back(inputSeq[i]);
}
if(v.size()==0)return 1;
sort(v.begin(),v.end());
long long sz=v.size();
sz--;
long long zs=sz;
long long ans=1ll;
for(int i=1;i<=zs;i++){
ans=(ans*stepen(sz,v[i]-v[i-1]-1ll))%MOD;
sz--;
}
if(zs==n)ans=(ans*(long long)n)%MOD;
return (int)ans;
}
