#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll MOD=1000000009;
ll safe_mod(ll n,ll p){
n%=p;
if(n<0)n+=p;
return n;
}
int valid(int n, int inputSeq[]){
int fix=MOD;
rep(i,n){
if(inputSeq[i]<=n){
if(fix==MOD)fix=safe_mod(i-inputSeq[i],n);
else{
if(fix!=safe_mod(i-inputSeq[i],n)){
return 0;
}
}
}
}
vector<bool> cnt(300000);
rep(i,n){
if(cnt[inputSeq[i]])return 0;
cnt[inputSeq[i]]=1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int cnt=0;
vector<int> repl(300000,-1);
rep(i,n){
repl[gondolaSeq[i]]=i;
}
int fix=0;
vector<bool> inc(n,0);
rep(i,n){
if(gondolaSeq[i]<=n){
fix=safe_mod(i-gondolaSeq[i],n);
inc[i]=1;
}
}
vector<int> gdls(n);
rep(i,n){
gdls[i]=safe_mod(i-fix,n);
if(gdls[i]==0)gdls[i]=n;
}
int gdl=n+1;
int pos=0;
while(pos<n&&inc[pos])pos++;
while(true){
if(pos==n)break;
if(repl[gdl]==-1){
replacementSeq[cnt]=gdls[pos];
gdls[pos]=gdl;
}
else{
replacementSeq[cnt]=gdls[repl[gdl]];
gdls[repl[gdl]]=gdl;
inc[repl[gdl]]=1;
}
cnt++;
gdl++;
while(pos<n&&inc[pos])pos++;
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)){
return 0;
}
ll ans=n;
int can=n;
int cnt=0;
vector<int> repl(300000,-1);
rep(i,n){
repl[inputSeq[i]]=i;
}
int fix=0;
vector<bool> inc(n,0);
rep(i,n){
if(inputSeq[i]<=n){
fix=safe_mod(i-inputSeq[i],n);
ans=1;
can--;
inc[i]=1;
}
}
vector<int> gdls(n);
rep(i,n){
gdls[i]=safe_mod(i-fix,n);
if(gdls[i]==0)gdls[i]=n;
}
int gdl=n+1;
int pos=0;
while(pos<n&&inc[pos])pos++;
while(true){
if(pos==n)break;
if(repl[gdl]==-1){
ans*=can;
ans=safe_mod(ans, MOD);
gdls[pos]=gdl;
}
else{
gdls[repl[gdl]]=gdl;
inc[repl[gdl]]=1;
can--;
}
cnt++;
gdl++;
while(pos<n&&inc[pos])pos++;
}
return ans;
}
