#include "gondola.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef int ll;
typedef long long lll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
int valid(int n, int inputSeq[])
{
ll sus = -1;
set<ll> realsus;
FOR(i,0,n){
realsus.insert(inputSeq[i]);
if (inputSeq[i] <= n){
sus = i;
}
}
if (realsus.size() != n) return 0;
if (sus==-1) return 1;
ll cnt = inputSeq[sus];
FOR(i, sus, sus+n){
if (cnt > n) cnt -= n;
ll imp = i;
if (imp>=n) imp -= n;
if (inputSeq[imp] != cnt && inputSeq[imp] <= n) return 0;
cnt++;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<ll> sussy(n);
ll sus = -1;
FOR(i,0,n){
if (gondolaSeq[i] <= n){
sus = i;
}
}
ll cnt = gondolaSeq[sus];
if (sus==-1) sus = 0, cnt = 1;
FOR(i,sus,sus+n){
if (cnt>n) cnt-=n;
sussy[i%n] = cnt;
cnt++;
}
ll maxi = -1;
ll maxpos = -1;
FOR(i,0,n){
if (gondolaSeq[i] > maxi){
maxpos = i;
maxi = max(maxi, gondolaSeq[i]);
}
}
vector<ll> stuff(maxi-n);
FOR(i,0,maxi-n) stuff[i] = -1;
FOR(i,0,n){
if (gondolaSeq[i] > n){
stuff[gondolaSeq[i]-n-1] = i;
}
}
FOR(i,0,maxi-n){
if (stuff[i] != -1){
replacementSeq[i] = sussy[stuff[i]];
sussy[stuff[i]] = i+n+1;
}else{
replacementSeq[i] = sussy[maxpos];
sussy[maxpos] = i+n+1;
}
}
return maxi-n;
}
//----------------------
unordered_map<ll,ll> cache;
lll fastexp(lll n, lll e, lll p){
if (e==0) return 1;
if (e==1) return n;
if (e==2) return n*n % p;
if (e%2==0){
lll a = fastexp(n, e/2, p);
return a*a%p;
}else{
lll a = fastexp(n, e-1, p);
return a*n%p;
}
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
ll maxi = 0;
FOR(i,0,n) maxi = max(maxi, inputSeq[i]);
if (maxi <= n) return 1;
ll mini = 1000000000;
FOR(i,0,n) mini = min(mini, inputSeq[i]);
long long ans = 1;
if (mini > n) ans*= n;
ll sus = n;
unordered_set<ll> imp;
FOR(i,0,n) imp.insert(inputSeq[i]);
FOR(i,0,n) if (inputSeq[i] <= n) sus -= 1;
vector<ll> torn;
FOR(i,0,n) torn.push_back(inputSeq[i]);
torn.push_back(n);
sort(torn.begin(), torn.end());
FOR(i,1,n+1){
if (torn[i] <= n) continue;
ans *= max((lll) 1, fastexp(sus,torn[i]-torn[i-1]-1,1000000009));
ans %= 1000000009;
sus--;
}
return ans%1000000009;
}
