#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int arr[]){
unordered_set<int>se;
bool amos=true;
deque<int>d;
int mini=INT_MAX;
set<int>shift;
for(int x=0;x<n;x++){
if(se.find(arr[x])!=se.end()) amos=false;
se.insert(arr[x]);
if(arr[x]<=n){
d.push_back(arr[x]);
mini=min(mini,arr[x]);
if(arr[x]>=x+1){
shift.insert(arr[x]-(x+1));
}
else{
shift.insert(arr[x]+n-(x+1));
}
}
}
if(shift.size()>1) amos=false;
return amos;
}
int replacement(int n, int arr[], int ans[]){
int maxi=0;
int shift=-1;
deque<int>d;
for(int x=0;x<n;x++){
maxi=max(maxi,arr[x]);
if(arr[x]<=n){
if(arr[x]>=x+1){
shift=arr[x]-(x+1);
}
else{
shift=arr[x]+n-(x+1);
}
}
d.push_back(arr[x]);
}
while(shift>0){
shift--;
d.push_front(d.back());
d.pop_back();
}
vector<pair<int,int>>v;
for(int x=0;x<n;x++){
if(d[x]>n){
v.push_back({d[x],x});
}
}
sort(v.begin(),v.end());
int index=0;
int cur=n;
for(auto it:v){
bool done=true;
while(cur<it.first){
if(done){
ans[index]=it.second+1;
done=false;
index++;
}
else{
ans[index]=cur;
index++;
}
cur++;
}
}
return maxi-n;
}
//----------------------
long long mod=1000000009;
long long f(long long a, long long b){
if(a==1||b==0) return 1;
if(b==1) return a;
int hold=f((a*a)%mod,b/2);
if(b%2) hold=(hold*a)%mod;
return hold;
}
int countReplacement(int n, int arr[]){
int arr2[n];
for(int x=0;x<n;x++) arr2[x]=arr[x];
if(valid(n,arr2)==0) return 0;
int maxi=0;
vector<int>v;
int mini=INT_MAX;
for(int x=0;x<n;x++){
maxi=max(maxi,arr[x]);
mini=min(mini,arr[x]);
if(arr[x]>n)v.push_back(arr[x]);
}
if(maxi==n) return 1;
int cur=n;
long long counter=1;
sort(v.begin(),v.end());
int sz=v.size();
for(auto it:v){
long long gap=max(0,it-cur-1);
gap%=mod;
counter=(counter*f(sz,gap))%mod;
cur=it;
sz--;
}
if(mini>n){
counter=(counter*n)%mod;
}
return counter;
}
//
