#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+9;
ll cpow(ll a, ll b) {
ll res = 1;
for(;b;b>>=1,a=a*a%mod)
if(b & 1) res = res*a % mod;
return res;
}
int valid(int n, int inputSeq[]) {
vector<int> tocheckunique(n);
bool rotated = 0;
for(int i=0;i<n;i++) tocheckunique[i] = inputSeq[i];
for(int i=0;i<n;i++) {
if(inputSeq[i] <= n) {
rotated = 1;
rotate(inputSeq, inputSeq+((i-(inputSeq[i]-1) < 0 ? n : 0) + i-(inputSeq[i]-1)), inputSeq+n);
break;
}
}
//cout << "bruh";
sort(tocheckunique.begin(), tocheckunique.end());
if(unique(tocheckunique.begin(), tocheckunique.end()) - tocheckunique.begin() != n) return 0;
//rotate(inputSeq, inputSeq+1, inputSeq+n);
if(!rotated) return 1;
bool yes = 1;
for(int i=0;i<n;i++) {
if(inputSeq[i] <= n)
yes &= (inputSeq[i] == i+1);
}
return yes;
}
//----------------------
int cval[100005];
int bruhpos[250005];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
if(!valid(n, gondolaSeq)) return -69420;
//its valid but like just incaseor smth lol
for(int i=0;i<n;i++) {cval[i] = i+1;}
int ptr = 0;
memset(bruhpos, -1, sizeof bruhpos);
pair<int, int> bruhbruh(INT_MIN, -1);
for(int i=0;i<n;i++) {
if(gondolaSeq[i] > n) {
bruhpos[gondolaSeq[i]] = i;
bruhbruh = max(bruhbruh, {gondolaSeq[i], i});
}
}
for(int i=n+1;i<=bruhbruh.first;i++) {
if(bruhpos[i] == -1) {
replacementSeq[ptr++] = cval[bruhbruh.second];
cval[bruhbruh.second] = i;
} else {
replacementSeq[ptr++] = cval[bruhpos[i]];
cval[bruhpos[i]] = i;
}
}
return ptr;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
ll res = 1;
vector<int> pospospos(1, n);
for(int i=0;i<n;i++) {
if(inputSeq[i] > n) {
pospospos.push_back(inputSeq[i]);
}
}
sort(pospospos.begin(), pospospos.end());
if(*min_element(inputSeq, inputSeq+n) > n) res = n;
for(int i=1;i<pospospos.size();i++) {
res = (res * cpow(pospospos.size()-i, pospospos[i] - pospospos[i-1] - 1)) % mod;
}
return res;
}
