#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+9;
int marc[maxn], pos[maxn], onde[maxn], need[maxn];
map<int,int>help;
int valid(int n, int v[])
{
int val, ini=-1;
help.clear();
for(int i=0;i<n;i++){
if(help[v[i]]>0) return 0;
help[v[i]]++;
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
if(ini==-1) return 1;
for(int i=ini+1;i<n;i++){
if(help[v[i]]) return 0;
help[v[i]]++;
val++; val%=(n+1);
if(!val) val++;
if(v[i]>n) continue;
if(val!=v[i]) return 0;
}
return 1;
}
int replacement(int n, int v[], int resp[])
{
int maior=1;
for(int i=0;i<n;i++) maior=max(maior,v[i]);
for(int i=1;i<=maior;i++) need[i]=pos[i]=marc[i]=0;
int val, ini=-1;
for(int i=0;i<n;i++){
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
if(ini==-1){
for(int i=1;i<=n;i++){
pos[i-1]=i;
onde[i]=i-1;
}
}else{
int og=val;
for(int i=ini;i<n;i++){
pos[i]=val;
onde[val]=i;
val++; val%=(n+1);
if(!val) val++;
}
val=og;
for(int i=ini;i>=0;i--){
pos[i]=val;
onde[val]=i;
val--;
if(!val) val+=n;
}
}
for(int i=0;i<n;i++){
marc[v[i]]++;
need[v[i]]=i;
}
int id=0;
set<pair<int,int>>tira; // cara e onde ele tá
for(int i=1;i<=n;i++) if(!marc[i]) tira.insert({i,onde[i]});
for(int i=n+1;i<=maior;i++){
if(!marc[i]){ // posso colocar em qlqr lugar
auto f=tira.begin();
resp[id]=f->first;
int lugar=f->second;
onde[i]=lugar;
pos[lugar]=i;
tira.erase(f);
id++;
tira.insert({i,onde[i]});
}else{ // tenho q colocar no lugar certo
int at=pos[need[i]];
tira.erase({at,onde[at]});
pos[need[i]]=i;
resp[id]=at;
id++;
}
}
return id;
}
ll pot(ll x, ll y){
if(y==0) return 1;
if(y==1) return x;
ll at=pot(x,y/2); at%=mod;
at*=at; at%=mod;
at*=pot(x,y%2); at%=mod;
return at;
}
int countReplacement(int n, int v[])
{
if(!valid(n,v)) return 0;
int ini=-1;
for(int i=0;i<n;i++){
if(v[i]<=n) ini=i;
}
ll resp=1;
if(ini==-1) resp=n;
vector<ll>process;
for(int i=0;i<n;i++) if(v[i]>n) process.push_back((ll)v[i]);
sort(process.begin(),process.end());
ll a=process.size(), last=n;
for(ll b : process){
resp*=pot(a,b-last-1); resp%=mod;
last=b; a--;
}
return resp;
}
