#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl
#define v first
#define pos second
#define MAX 1000000009
vector<pair<lli, lli>> arr;
unordered_map<lli,lli> mapa;
lli val,ult,a,res,libres;
int valid(int n, int inputSeq[])
{
ult = -1;
val = -1;
bool res,iguales = false;
rep(i,0,n-1) {
if (inputSeq[i] <= n) {
ult = i;
val = inputSeq[i];
}
if (mapa[inputSeq[i]] == 1) {iguales = true; break;}
else mapa[inputSeq[i]] = 1;
}
if (iguales) return 0;
if (ult == -1) return 1;
val -= ult;
if(val < 1) val += n;
res = true;
rep(i,0,n-1) {
if (inputSeq[i] <= n){
if (inputSeq[i] != val) {res = false; break;}
}
val++;
if (val > n) val = 1;
}
return res;
}
lli valEn (lli p, lli n) {
lli b;
if (p < ult) {
b = val - (ult-p);
if (b < 1) b += n;
}
else {
b = val + (p-ult);
if (b > n) b -= n;
}
return b;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
val = -1;
ult = -1;
res = 0;
rep(i,0,n-1) {
if (gondolaSeq[i] <= n) {
ult = i;
val = gondolaSeq[i];
}
else arr.push_back({gondolaSeq[i],i});
a = gondolaSeq[i];
res = max(res,a);
}
sort(arr.begin(), arr.end());
if (val == -1) {
ult = 0;
val = 1;
}
lli pas = n;
lli cont = 0;
for (auto act : arr) {
a = valEn(act.pos,n);
rep(i,pas+1,act.v){
replacementSeq[cont] = a;
a = i;
cont++;
}
pas = act.v;
}
res -= n;
return res;
}
lli expo(lli num, lli e) {
lli r = 1;
while (e > 0) {
if (e&1) {
r *= num;
r %= MAX;
}
num *= num;
num %= MAX;
e /= 2;
}
return r;
}
int countReplacement(int n, int inputSeq[])
{
bool iguales = false;
val = -1;
ult = -1;
res = 0;
libres = n;
rep(i,0,n-1) {
if (inputSeq[i] <= n) {
if (ult == -1) {
ult = i;
val = inputSeq[i];
}
else {
a = valEn(i,n);
if (a != inputSeq[i]) return 0;
}
libres--;
}
else arr.push_back({inputSeq[i],i});
if (mapa[inputSeq[i]] == 1) {iguales = true; break;}
else mapa[inputSeq[i]] = 1;
}
if (iguales) return 0;
sort(arr.begin(), arr.end());
if (val == -1) {
res = n;
val = 1;
ult = 0;
}
else res = 1;
lli pas = n;
for (auto act : arr) {
a = act.v - pas - 1;
a = expo(libres,a);
res *= a;
res %= MAX;
libres--;
pas = act.v;
}
return res;
}
