#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll pow(ll x, ll y, ll mod){
ll ans=1;
while (y != 0) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
const int N = 2.5e5 + 10, MOD = 1000000009;
int valid(int n, int inputSeq[])
{
int ls = -1, cnt = 0;
map<int, int> mp;
for(int i = 0; i < n; i++){
cnt++;
if(mp[inputSeq[i]]) return 0;
mp[inputSeq[i]] = 1;
if(inputSeq[i] <= n){
if(ls != -1 && (ls + cnt - 1) % n + 1 != inputSeq[i]) return 0;
ls = inputSeq[i];
cnt = 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int cyc = 1, mx = 0;
map<int, int> mp;
for(int i = 0; i < n; i++){
mx = max(mx, gondolaSeq[i]);
if(gondolaSeq[i] <= n){
cyc = (n + gondolaSeq[i] - i) % n;
}
}
for(int i = 0; i < n; i++){
mp[gondolaSeq[i]] = (n + i + cyc - 1) % n + 1;
}
for(int i = n + 1; i <= mx; i++){
if(mp[i]) replacementSeq[i - n - 1] = mp[i];
else{
replacementSeq[i - n - 1] = mp[mx];
mp[mx] = i;
}
}
return mx - n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
ll ans = 1;
int k = 0;
vector<int> vec = {n};
for(int i = 0; i < n; i++){
if(inputSeq[i] > n) k++, vec.push_back(inputSeq[i]);
}
sort(vec.begin(), vec.end());
for(int i = 1; i <= k; i++){
ans = ans * pow(k - i + 1, vec[i] - vec[i - 1] - 1, MOD) % MOD;
}
return ans;
}
