#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 3e5 + 10;
const ll MOD = 1e9 + 9;
int num[MAXN];
map<ll, int> marc;
int id(int x, int n){
if(x == -1) return n - 1;
if(x == n) return 0;
return x;
}
int check_valid(int n, int inputSeq[]){
marc.clear();
for(int i=0; i<n; i++){
marc[inputSeq[i]] ++;
if(marc[inputSeq[i]] > 1) return 0;
}
int pos = n - 1;
for(int i=0; i<n; i++){
if(inputSeq[i] <= n){
pos = min(pos, i);
}
}
num[pos] = inputSeq[pos];
if(num[pos] > n) num[pos] = 1;
int cur_num = num[pos] - 1;
int cur_pos = id(pos - 1, n);
while(cur_num > 0){
num[cur_pos] = cur_num;
cur_num --; cur_pos = id(cur_pos - 1, n);
}
cur_num = num[pos] + 1;
cur_pos = id(pos + 1, n);
while(cur_num <= n){
num[cur_pos] = cur_num;
cur_num ++; cur_pos = id(cur_pos + 1, n);
}
for(int i=0; i<n; i++){
if(inputSeq[i] <= n && inputSeq[i] != num[i]){
return 0;
}
}
return 1;
}
int valid(int n, int inputSeq[]){
return check_valid(n, inputSeq);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int pos = n - 1;
for(int i=0; i<n; i++){
if(gondolaSeq[i] <= n){
pos = min(pos, i);
}
}
num[pos] = gondolaSeq[pos];
int cur_num = gondolaSeq[pos] - 1;
int cur_pos = id(pos - 1, n);
while(cur_num > 0){
num[cur_pos] = cur_num;
cur_num --; cur_pos = id(cur_pos - 1, n);
}
cur_num = gondolaSeq[pos] + 1;
cur_pos = id(pos + 1, n);
while(cur_num <= n){
num[cur_pos] = cur_num;
cur_num ++; cur_pos = id(cur_pos + 1, n);
}
vector<pair<int, int>> v;
for(int i=0; i<n; i++){
if(gondolaSeq[i] > n){
v.push_back({gondolaSeq[i], num[i]});
}
}
sort(v.begin(), v.end());
int l = 0;
int cur = n + 1;
for(auto [x, i] : v){
replacementSeq[l ++] = i;
while(cur != x){
replacementSeq[l ++] = cur;
cur ++;
}
cur ++; // x nao quebra
}
// for(int i=0; i<l; i++) cout << replacementSeq[i] << " ";
// cout << "\n";
return l;
}
ll exp(ll a, ll b){
ll r = 1;
for(int i=32; i>=0; i--){
r = (r * r) % MOD;
if(b & (1ll << i)) r = (r * a) % MOD;
}
return r;
}
int countReplacement(int n, int inputSeq[]){
if(!check_valid(n, inputSeq)) return 0;
vector<ll> v;
for(int i=0; i<n; i++){
if(inputSeq[i] > n){
v.push_back((ll) inputSeq[i]);
}
}
sort(v.begin(), v.end());
ll ans = 1;
ll last = n + 1;
for(ll i=0; i<(int) v.size(); i++){
ans = (ans * exp(v.size() - i, v[i] - last)) % MOD;
last = v[i] + 1;
}
// cout << ans << endl;
bool ok = false;
for(int i=0; i<n; i++){
if(inputSeq[i] <= n){
ok = true;
}
}
if(!ok) ans = (ans * n) % MOD;
return ans;
}
