#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
ll mod=((ll)1000000000)+9;
map<int, int> cnt_valid;
int valid(int n, int inputSeq[])
{
int i,j;
for(i=0;i<n;i++)if(inputSeq[i]<=n)break;
if(i<n)for(j=0;j<n;j++)if(inputSeq[j]<=n&&(inputSeq[j]+i)%n!=(inputSeq[i]+j)%n)return 0;
std::sort(inputSeq,inputSeq+n);
for(i=1;i<n;i++)if(inputSeq[i-1]==inputSeq[i])return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int pt=0, crd=0;
for(int i=0; i<n; i++){
if(gondolaSeq[i]<=n){
pt=gondolaSeq[i], crd=i; break;
}
}
int initial[100010];
if(pt==0){
for(int i=0; i<n; i++){
initial[i]=i+1;
}
}
else{
for(int i=crd-pt+1, cnt=1; cnt<=n; i++){
i+=n;
i%=n;
initial[i]=cnt;
cnt++;
}
}
set<pii> s;
for(int i=0; i<n; i++){
if(gondolaSeq[i]>n){
s.insert({gondolaSeq[i], i} );
}
}
if(s.empty()){
return 0;
}
int cnt=n+1;
for(auto it=s.begin(); it!=s.end(); it++){
while(cnt<(it->ft) ){
replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt; cnt++;
}
replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt;
cnt++;
}
return cnt-1-n;
}
//----------------------
ll exp(ll x, ll e){
if(e==0){
return 1;
}
if(e==1){
return x%mod;
}
return (exp(x, e%2)*(exp( (x*x)%mod, e/2) ) )%mod ;
}
int countReplacement(int n, int inputSeq[])
{
ll p=n;
if(valid(n, inputSeq)==0){
return 0;
}
multiset<ll> s;
for(int i=0; i<n; i++){
if(inputSeq[i]>n){s.insert({inputSeq[i]});}
else{
p--;
}
}
ll ac=n+1;
ll res=1;
if( p==n ){
res=n;
}
for(auto it=s.begin(); it!=s.end(); it++){
res=(res*( exp(p, ((*it)-1)-ac+1 ) ) )%mod; ac=(*it)+1; p--;
}
return res;
}
