#include "gondola.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef int ll;
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;
}
//----------------------
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 sus = n;
long long ans = 1;
set<ll> imp;
FOR(i,0,n) imp.insert(inputSeq[i]);
FOR(i,0,n) if (inputSeq[i] <= n) sus -= 1;
FOR(i,n+1, maxi+1){
if (imp.count(i)){
sus -= 1;
continue;
} else{
ans *= sus;
ans %= 1000000009;
}
}
return ans;
}
