#include <bits/stdc++.h>
#include "gondola.h"
#define ll long long
using namespace std;
const int MOD=1000000009;
ll binpow (int a, int b)
{
ll ans=1;
while (b)
{
if (b&1)
{
ans=(1LL*ans*a)%MOD;
}
a=(1LL*a*a)%MOD;
b>>=1;
}
return ans;
}
int valid (int n, int ins[])
{
int prviidx=-1;
set <int> s;
for (int i=0; i<n; i++) s.insert(ins[i]);
if ((int)s.size()<n) return 0;
for (int i=0; i<n; i++)
{
if (ins[i]<=n)
{
prviidx=i;
break;
}
}
if (prviidx==-1) return 1;
int trn=ins[prviidx];
bool f=true;
for (int i=prviidx+1; i<n; i++)
{
trn++;
trn%=n;
if (trn==0) trn=n;
if (ins[i]!=trn && ins[i]<=n)
{
f=false;
break;
}
}
if (f) return 1;
else return 0;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int prviidx=-1;
for (int i=0; i<n; i++)
{
if (gondolaSeq[i]<=n)
{
prviidx=i;
break;
}
}
int prvibr=1;
if (prviidx!=-1)
{
prvibr=(gondolaSeq[prviidx]-prviidx)%n;
if (prvibr<=0) prvibr+=n;
}
vector <int> orig(n);
for (int i=0; i<n; i++)
{
orig[i]=(prvibr+i)%n;
if (orig[i]==0) orig[i]=n;
}
set <pair<int, int>> fali;
for (int i=0; i<n; i++)
{
if (gondolaSeq[i]>n) fali.insert({gondolaSeq[i], orig[i]});
}
int trn=n+1;
int cnt=0;
for (auto i: fali)
{
if (i.first>trn)
{
int donji=i.second;
while (trn!=i.first+1)
{
replacementSeq[cnt]=donji;
donji=trn;
trn++;
cnt++;
}
}
else
{
replacementSeq[cnt]=i.second;
trn++;
cnt++;
}
}
return cnt;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
vector <int> veci;
int koliko=0;
for (int i=0; i<n; i++)
{
if (inputSeq[i]>n)
{
veci.push_back(inputSeq[i]);
koliko++;
}
}
sort (veci.begin(), veci.end());
ll ans=1;
for (int i=0; i<veci.size(); i++)
{
int raz;
if (i==0) raz=veci[i]-n;
else raz=veci[i]-veci[i-1];
ans*=binpow(koliko, raz-1);
ans%=MOD;
koliko--;
}
if (veci.size()<n) return ans;
else return (1LL*ans*n)%MOD;
}
