#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];
int valid(int n, int inputSeq[])
{
bool v=true;
int mn=INT_MAX;
int idx=-1;
for(int i=0;i<n;i++){
cnt[inputSeq[i]]++;
if(cnt[inputSeq[i]]>1) v=false;
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;
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++;
}
int mx=*max_element(a+1,a+n+1);
for(int i=n+1;i<=mx;i++) cnt[i]=0;
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;
suf[a[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;
long long ans=1;
for(int i=mx-1;i>=n+1;i--) suf[i]+=suf[i+1];
for(int i=n+1;i<=mx;i++){
//cout<<cnt[i] <<" ";
if(cnt[i]==0) ans*=suf[i],ans%=MOD;
}
return ans;
}
