#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+9;
const int N=3e5+10;
long long cnt[N],a[N],suf[N];
set<long long> change;
long long modofpow(long long n,long long p){
long long mult=n,ans=1;
while(p){
if(p%2LL==1LL) ans*=mult,ans%=MOD;
p/=2LL;
mult=mult*mult;
mult%=MOD;
}
return ans;
}
int valid(int n, int inputSeq[])
{
bool v=true;
int mn=INT_MAX;
int idx=-1;
set<int> s;
for(int i=0;i<n;i++){
if(s.find(inputSeq[i])!=s.end()) v=false;
s.insert(inputSeq[i]);
if(inputSeq[i]>n) continue;
if(mn>inputSeq[i]){
mn=inputSeq[i];
idx=i;
}
}
int now;
if(idx!=-1){
now=inputSeq[idx];
for(int i=idx;i<idx+n;i++,now++){
int con=i%n;
if(inputSeq[con]>n) continue;
if(inputSeq[con]!=now){
v=false;
}
}
}
return v;
}
//----------------------
int replacement(int n, int gondolaSeq[], int ans[])
{
int idx=n;
for(int i=0;i<n;i++){
if(gondolaSeq[i]>n) continue;
idx=i;
break;
}
int pt=gondolaSeq[idx];
if(idx!=n) for(int i=idx;i<idx+n;i++){
int con=(pt-1)%n+1;
a[con]=gondolaSeq[i%n];
pt++;
}
if(idx==n) for(int i=1;i<=n;i++) a[i]=gondolaSeq[i-1];
for(int i=1;i<=n;i++){
if(a[i]<=n) continue;
cnt[a[i]]=i;
}
int mx=*max_element(a+1,a+n+1);
int now=cnt[mx];
for(int i=mx;i>n;i--){
if(cnt[i]==0) cnt[i]=now;
if(cnt[i]!=now) now=cnt[i];
}
// for(int i=n+1;i<=mx;i++) cout<<cnt[i] <<" ";
// cout<<"\n";
int len=mx-n;
for(int i=1;i<=n;i++) a[i]=i;
for(int i=n+1;i<=mx;i++){
int ansidx=i-n-1;
ans[ansidx]=a[cnt[i]];
a[cnt[i]]=i;
}
return len;
}
//----------------------
int countReplacement(int n, int gondolaSeq[])
{
if(!valid(n,gondolaSeq)) return 0;
bool cyc=true;
for(int i=0;i<n;i++) if(gondolaSeq[i]<=n) cyc=false;
int idx=n;
for(int i=0;i<n;i++){
if(gondolaSeq[i]>n) continue;
idx=i;
break;
}
int pt=gondolaSeq[idx];
if(idx!=n) for(int i=idx;i<idx+n;i++){
int con=(pt-1)%n+1;
a[con]=gondolaSeq[i%n];
pt++;
}
if(idx==n) for(int i=1;i<=n;i++) a[i]=gondolaSeq[i-1];
for(int i=1;i<=n;i++){
if(a[i]<=n) continue;
change.insert(a[i]);
}
// for(int i=n+1;i<=mx;i++) cout<<cnt[i] <<" ";
// cout<<"\n";
long long ans=1;
if(!change.empty()) ans=modofpow((long long)(change.size()),((*change.begin())-((long long)n+1LL)));
long long tmp=change.size();
for(auto it=change.begin();it!=change.end();it++){
tmp--;
auto nxt=it;
nxt++;
if(nxt==change.end()) break;
ans*=modofpow(tmp,*nxt-*it-1LL);
ans%=MOD;
}
if(cyc) ans*=(long long)n,ans%=MOD;
return ans;
}
