#include "gondola.h"
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
const int MOD=1e9+9;
int valid(int n, int inputSeq[])
{
int shift=-1;
std::set<int> used;
for(int i=0;i<n;i++){
if(used.count(inputSeq[i])) return 0;
used.insert(inputSeq[i]);
if(inputSeq[i]<=n){
int new_shift=(inputSeq[i]-i+n)%n;
if(shift!=-1&&shift!=new_shift) return 0;
shift=new_shift;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i=0;i<n;i++){
gondolaSeq[i]--;
}
int shift=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<n){
shift=(gondolaSeq[i]-i+n)%n;
break;
}
}
std::vector<int> seq(n);
for(int i=0;i<n;i++){
seq[i]=(i+shift)%n;
}
auto max=std::max_element(gondolaSeq,gondolaSeq+n);
std::vector<int> where(*max+1,max-gondolaSeq);
for(int i=0;i<n;i++){
where[gondolaSeq[i]]=i;
}
for(int x=n;x<=*max;x++){
replacementSeq[x-n]=seq[where[x]];
seq[where[x]]=x;
}
int l=*max+1-n;
for(int i=0;i<l;i++){
replacementSeq[i]++;
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq)) return 0;
for(int i=0;i<n;i++){
inputSeq[i]--;
}
int shift=-1;
for(int i=0;i<n;i++){
if(inputSeq[i]<n){
shift=(inputSeq[i]-i+n)%n;
break;
}
}
std::vector<int> seq(n);
for(int i=0;i<n;i++){
seq[i]=(i+shift+n)%n;
}
auto max=std::max_element(inputSeq,inputSeq+n);
std::vector<int> where(*max+1,max-inputSeq);
for(int i=0;i<n;i++){
where[inputSeq[i]]=i;
}
int cnt=(shift==-1)?n:1;
int spots=n;
for(int x=0;x<=*max;x++){
if(x==inputSeq[where[x]]){
spots--;
}else if(x>=n){
cnt=1LL*cnt*spots%MOD;
}
seq[where[x]]=x;
}
return cnt;
}
