#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 250005;
const int mod=1e9+9;
map<int,int> mp;
ll power(ll a,ll n){
ll res=1;
while(n){
if(n&1) res=(res*a)%mod;
a=(a*a) % mod;
n>>=1;
}
return res;
}
int valid(int n, int arr[]){
int start=-1;
for(int i=0; i < n;i++){
if(mp[arr[i]]) return 0;
mp[arr[i]]=true;
if(arr[i]<=n){
int curr=(i-arr[i]+1+n)%n;
if(start==-1) start=curr;
else if(start!=curr) return 0;
}
}
return 1;
}
int replacement(int n, int arr[], int res[]){
int start=0;
deque<int> dq(n);
for(int i=0; i < n;i++){
if(arr[i]<=n) start=(i-arr[i]+1+n)%n;
dq[i]=arr[i];
}
while(start){
dq.push_back(dq.front());
dq.pop_front();
start--;
}
vector<pair<int,int>> ans(n);
for(int i=0; i < n;i++){
ans[i]={dq[i],i};
}
sort(ans.begin(),ans.end());
int size=0;
int curr=n+1;
for(int i=0; i < n;i++){
if(ans[i].first<=n) continue;
res[size++]=ans[i].second+1;
while(curr < ans[i].first) res[size++]=curr++;
curr++;
}
return size;
}
int countReplacement(int n, int arr[]){
if(!valid(n,arr)) return 0;
vector<ll> vec;
ll curr=n;
ll res=1;
ll last=n;
for(int i=0; i < n;i++){
if(arr[i]<=n) curr--;
else vec.push_back(arr[i]);
}
sort(vec.begin(),vec.end());
if(curr==n) res=n;
for(ll x : vec){
res=(res*power(curr,x-last-1))%mod;
last=x;
curr--;
}
return int(res);
}
