// #pragma once
#include "gondola.h"
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
#define ll long long
ll powmod(ll a,ll b,ll mod)
{
if(b==0)
return 1;
if(b==1)
return a;
ll h=powmod(a,b/2,mod);
h=(h*h)%mod;
if(b&1)
h=(h*a)%mod;
return h;
}
int valid(int n, int a[])
{
int j=0;
bool adspl=1;
int val;
for(int i=0;i<n;i++)
{
a[i]--;
if(a[i]<=(n-1))
{
j=i;
val=a[j];
adspl=0;
}
}
int level[n];
int ok=j;
set<int> spp;
map<int,int> kidr;
int mx=0;
if(adspl)
val=0;
vector<int> nep;
bool posas=1;
for(int ap=0;ap<n;ap++)
{
level[j]=(val+ap)%n;
if(level[j]!=a[j])
{
nep.push_back(a[j]);
spp.insert(j);
if(kidr.find(a[j])!=kidr.end())
{
posas=0;
}
kidr[a[j]]=j;
if(a[j]<n)
{
posas=0;
}
mx=max(mx,a[j]);
}
j+=1;
j%=n;
}
return posas;
// sort(begin(nep),end(nep));
// ll last=n;
// for(int i=0;i<nep.size();i++)
// {
// }
for(int ne=n;ne<=mx;ne++)
{
if(kidr.find(ne)==kidr.end())
{
level[*begin(spp)]=ne;
}
else
{
int f=kidr[ne];
spp.erase(f);
}
}
if(spp.size()==0)
return 1;
return 0;
}
int replacement(int n, int a[], int ans[])// Done
{
int j=0;
bool adspl=1;
int val;
for(int i=0;i<n;i++)
{
a[i]--;
if(a[i]<=(n-1))
{
j=i;
val=a[j];
adspl=0;
}
}
int level[n];
int ok=j;
set<int> spp;
map<int,int> kidr;
int mx=0;
if(adspl)
val=0;
for(int ap=0;ap<n;ap++)
{
level[j]=(val+ap)%n;
if(level[j]!=a[j])
{
spp.insert(j);
kidr[a[j]]=j;
mx=max(mx,a[j]);
}
j+=1;
j%=n;
}
int l=0;
for(int ne=n;ne<=mx;ne++)
{
if(kidr.find(ne)==kidr.end())
{
// Place some random place
ans[l++]=level[*begin(spp)]+1;
level[*begin(spp)]=ne;
}
else
{
int f=kidr[ne];
spp.erase(f);
ans[l++]=level[f]+1;
}
}
return l;
}
int countReplacement(int n, int a[])
{
if(!valid(n,a))
return 0;
ll ans=1,mod=1e9+9;
int j=0;
bool adspl=1;
int val;
int mx=0;
for(int i=0;i<n;i++)
{
// a[i]--;
mx=max(mx,a[i]);
if(a[i]<=(n-1))
{
j=i;
val=a[j];
adspl=0;
}
}
int ok=j,level=0;
if(adspl)
{
val=0;
ans=n;
}
vector<int> vape;
for(int ap=0;ap<n;ap++)
{
level=(val+ap)%n;
if(level!=a[j])
{
vape.push_back(a[j]);
mx=max(mx,a[j]);
}
j+=1;
j%=n;
}
sort(begin(vape),end(vape));
ll last=n;
ll top=vape.size();
for(int i=0;i<vape.size();i++)
{
ll len=vape[i]-last;
ans=(ans*powmod(top,len,mod))%mod;
last=vape[i]+1;
top--;
}
return ans;
}
