#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
set<int> values;
int valid(int n, int inputSeq[])
{
bool valid=true;int last=-1;
for (int i=0;i<n;i++)
{
if (inputSeq[i]<=n and last==-1) {last=i;continue;}
if (inputSeq[i]>n) continue;
int diff=inputSeq[i]-inputSeq[last];
if (diff<0) diff+=n;
if (diff!=i-last) {valid=false;break;}
last=i;
}
for (int i=0;i<n;i++) values.insert(inputSeq[i]);
if (valid and (int)values.size()==n) return 1;
return 0;
}
#define MAXN 100001
int seq[MAXN];
vector<pair<int,int>> positions;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int pocetak=-1;
for (int i=0;i<n;i++)
{
if (gondolaSeq[i]<=n) {pocetak=i;break;}
}
int curr=gondolaSeq[pocetak];
for (int i=pocetak;i<n;i++)
{
seq[i]=curr;curr++;if (curr==n+1) curr=1;
}
for (int i=0;i<pocetak;i++)
{
seq[i]=curr;curr++;if (curr==n+1) curr=1;
}
for (int i=0;i<n;i++)
{
if (gondolaSeq[i]>n) positions.push_back({gondolaSeq[i],i});
}
sort(positions.begin(),positions.end());if ((int)positions.size()==0) return 0;
int pointer=0;curr=n+1;int pozicija=0;
while (pointer<(int)positions.size())
{
while (curr<=positions[pointer].first) {replacementSeq[pozicija]=seq[positions[pointer].second];seq[positions[pointer].second]=curr;curr++;pozicija++;}
pointer++;
}
return positions[(int)positions.size()-1].first-n;
}
vector<int> vec;
#define MOD 1000000009
long long binpow(int a,int b)
{
if (a==1) return 1;
a%=MOD;long long resenje=1;
while (b>0)
{
if (b%2==1) resenje=(resenje*a)%MOD;
a=(a*a)%MOD;b/=2;
}
return resenje;
}
int countReplacement(int n, int inputSeq[])
{
if (valid(n,inputSeq)==0) return 0;
for (int i=0;i<n;i++)
{
if (inputSeq[i]>n) vec.push_back(inputSeq[i]);
}
sort(vec.begin(),vec.end());int last=n;int curr=(int)vec.size();
long long answer=1;
if (curr==n) answer*=n;
else if (curr==n-1) answer*=2;
for (int pos:vec)
{
int number=pos-last-1;
answer*=binpow(curr,number);
if (answer>=MOD) answer%=MOD;
last=pos;curr--;
}
return (int)answer;
}
