#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int a[]){
map<int,int>ma;
int sma=1e9,smai;
for(int i=0;i<n;i++){
if(a[i]<sma) {
sma=a[i];
smai=i;
}
if(ma[a[i]]==1) return 0;
ma[a[i]]=1;
}
if(sma>n) return 1;
int num=sma;
for(int i=smai;i<n;i++){
if(num!=a[i] and a[i]<=n){
return 0;
}
num++;
}
for(int i=0;i<smai;i++){
if(num!=a[i] and a[i]<=n){
return 0;
}
num++;
}
return 1;
}
//----------------------
int replacement(int n, int a[], int replacementSeq []){
int sma=1e9,smai,ls,lsi=-1;
for(int i=0;i<n;i++){
if(a[i]<sma) {
sma=a[i];
smai=i;
}
}
if(sma>n){
// cout<<"Balls";
sma=1;
smai=0;
}
int num=sma;
for(int i=smai;i<n;i++){
if(a[i]>n){
replacementSeq[a[i]-n-1]=(num-1)%n+1;
if(a[i]-n-1>lsi){
// cout<<i<<' ';
ls=(num-1)%n+1;
lsi=a[i]-n-1;
}
}
num++;
}
for(int i=0;i<smai;i++){
if(a[i]>n){
replacementSeq[a[i]-n-1]=(num-1)%n+1;
if(a[i]-n-1>lsi){
// cout<<i<<' '<<a[i]-n-1<<' '<<num<<endl;
ls=(num-1)%n+1;
lsi=a[i]-n-1;
}
}
num++;
}
for(int i=0;i<lsi;i++){
if(replacementSeq[i]==0){
replacementSeq[i]=ls;
ls=n+1+i;
}
}
if(lsi!=-1)replacementSeq[lsi]=ls;
return lsi+1;
}
//----------------------
bool hmm[5000006];
int countReplacement(int n, int a[])
{
if(n==0) return 1;
long long int ans=1,nums=0,mod=1e9+9;
if(valid(n,a)==0) return 0;
int sma=1e9,smai,ls,lsi=-1;
for(int i=0;i<n;i++){
if(a[i]<sma) {
sma=a[i];
smai=i;
}
}
if(sma>n){
// cout<<"Balls";
sma=1;
smai=0;
ans=n;
}
int num=sma;
for(int i=smai;i<n;i++){
if(a[i]>n){
hmm[a[i]-n-1]=1;
nums++;
if(a[i]-n-1>lsi){
ls=(num-1)%n+1;
lsi=a[i]-n-1;
}
}
num++;
}
for(int i=0;i<smai;i++){
if(a[i]>n){
nums++;
hmm[a[i]-n-1]=1;
if(a[i]-n-1>lsi){
ls=(num-1)%n+1;
lsi=a[i]-n-1;
}
}
num++;
}
for(int i=0;i<lsi;i++){
if(hmm[i]==0){
ans*=nums;
ans%=mod;
}
else nums--;
}
return ans;
}
