#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
map<int,int> idk;
for(int i=0;i<n;i++)
{
if(idk[inputSeq[i]])
return 0;
idk[inputSeq[i]]++;
}
for(int i=0;i<n;i++)
{
if(inputSeq[i] <= n)
{
for(int j=0;j<n;j++)
{
if(inputSeq[(i+j)%n]<=n && inputSeq[(i+j)%n] != (inputSeq[i]-1 + j)%n + 1)
return 0;
}
return 1;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i=0;i<n;i++)
gondolaSeq[i]--;
vector<int> init(n),init_poz(250000,-1),final_poz(250000,-1);
int maxv=-1;
for(int i=0;i<n;i++)
{
final_poz[gondolaSeq[i]]=i;
maxv = max(maxv, gondolaSeq[i]);
}
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<n || i==n-1)
{
for(int j=0;j<n;j++)
init[(i+j)%n] = (gondolaSeq[i]+j)%n;
for(int j=0;j<n;j++)
init_poz[init[j]]=j;
int lun=0;
for(int j=n;j<=maxv;j++)
{
if(final_poz[j]==-1)
{
bool gasit=0;
for(int u=0;u<n;u++)
{
if(final_poz[init[u]] == -1)
{
replacementSeq[lun++] = init[u];
init[u] = j;
init_poz[j] = u;
init_poz[replacementSeq[lun-1]] = -1;
gasit=1;
break;
}
}
assert(gasit);
}
else
{
replacementSeq[lun++] = init[final_poz[j]];
init[final_poz[j]] = j;
init_poz[j] = final_poz[j];
init_poz[replacementSeq[lun-1]] = -1;
}
}
for(int i=0;i<lun;i++)
replacementSeq[i]++;
return lun;
}
}
assert(0);
}
//----------------------
#define ll long long
const ll MOD = 1e9+9;
ll put(ll a, ll exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put(a*a%MOD,exp/2);
else
return put(a*a%MOD,exp/2)*a%MOD;
}
int countReplacement(int n, int gondolaSeq[])
{
if(!valid(n,gondolaSeq))
return 0;
for(int i=0;i<n;i++)
gondolaSeq[i]--;
bool all_big=1;
vector<int> ap;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<n)
{
all_big=0;
continue;
}
ap.push_back(gondolaSeq[i]);
}
ll rez=put((ll)ap.size(), ap[0]-n);
for(int j=1;j<ap.size();j++)
{
rez = rez * put((ll)ap.size()-j, ap[j]-ap[j-1]-1);
}
/*for(int j=n;j<=maxv;j++)
{
if(!ap[j])
{
assert(cnt>0);
rez = rez*cnt%MOD;
}
else
{
cnt--;
}
}*/
if(all_big)
rez = rez*n%MOD;
return rez;
}
