#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
map<int,int> mp;
int p = -1;
for (int i = 0; i < n; ++i)
{
if (mp[inputSeq[i]]) return 0;
mp[inputSeq[i]]++;
}
for (int i = 0; i < n; i++){
if (inputSeq[i]<=n){
p=i;
break;
}
}
if (p==-1) return 1;
for (int i = 0; i < n; i++){
if (inputSeq[i]>n) continue;
int step = i-p;
if (i<p) step = n-p+i;
int a = inputSeq[p]-1;
a+=step;
a%=n;
a++;
if (inputSeq[i]!=a) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
pair<int,int> v[n];
for (int i = 0; i < n; ++i)
{
v[i]={gondolaSeq[i],i};
}
sort(v,v+n);
int cnt = 0;
int p = 0;
for (int i = 0; i < n; i++){
if (gondolaSeq[i]<=n){
p=i-gondolaSeq[i]+1;
if (p<0) p+=n;
break;
}
}
for (int i = 0; i < n; i++){
if (v[i].first<=n) continue;
int lel = v[i].second-p+1;
if (v[i].second<p) lel = n-p+v[i].second+1;
while (cnt<v[i].first-n) {
replacementSeq[cnt]=lel;
lel=cnt+n+1;
cnt++;
}
}
return cnt;
}
//----------------------
constexpr int MOD = 1e9+9;
int fpow(int base, int pow){
int rval = 1;
while (pow){
if (pow&1){
rval=(1LL*rval*base)%MOD;
}
base=(1LL*base*base)%MOD;
pow>>=1;
}
return rval;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n,inputSeq)) return 0;
pair<int,int> v[n];
int kapali = 0;
int ans = n;
for (int i = 0; i < n; ++i)
{
if (inputSeq[i]>n) {
kapali++;
}
v[i]={inputSeq[i],i};
}
if (kapali!=n) ans=1;
sort(v,v+n);
int cnt = 0;
for (int i = 0; i < n; i++){
if (v[i].first<=n) continue;
int kal = n-i;
ans=(1LL*ans*fpow(kal,max(0,v[i].first-n-cnt-1)))%MOD;
cnt=v[i].first-n;
while (cnt<v[i].first-n) {
cnt++;
}
}
return ans;
}
