#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MD = 1e9 + 9;
int valid(int n, int a[]){
int mn = INT_MAX, p;
set<int> s;
for(int i = 0;i<n;i++){
if(s.find(a[i]) != s.end()) return 0;
s.insert(a[i]);
if(a[i] < mn){
mn = a[i];
p = i;
}
}
if(mn > n) return 1;
for(int i = 0;i<n;i++){
int pos = (i + p) % n;
if(a[pos] <= n && a[pos] != mn + i) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int a[], int r[]){
int l = 0;
vector<int> og(n, -1);
vector<pair<int, int>> p;
bool f = 0;
for(int i = 0;i<n;i++){
if(a[i] <= n && !f){
og[i] = a[i];
for(int j = i + 1;j<n;j++) og[j] = og[j - 1] + 1;
if(og[0] == -1){
og[0] = og[n - 1] + 1;
for(int j = 1;j<i;j++) og[j] = og[j - 1] + 1;
}
f = 1;
}else if(a[i] > n){
p.push_back({a[i], i});
}
}
if(og[0] == -1){
for(int i = 0;i<n;i++) og[i] = i + 1;
}
for(int i = 0;i<n;i++){
og[i]--;
og[i] %= n;
og[i]++;
}
int cur = n + 1;
sort(p.begin(), p.end());
for(int i = 0;i<p.size();i++){
auto [d, id] = p[i];
r[l++] = og[id];
while(cur < d){
r[l++] = cur;
++cur;
}
++cur;
}
return l;
}
//----------------------
int countReplacement(int n, int a[]){
if(!valid(n, a)) return 0;
int mx = 0;
bool f = 0;
vector<ll> v;
for(int i = 0;i<n;i++){
if(a[i] <= n) f = 1;
else v.push_back(a[i]);
mx = max(mx, a[i]);
}
ll ans, lf = v.size();
if(f) ans = 1;
else ans = n;
auto pw = [](ll b, ll exp){
ll res = 1;
while(exp){
if(exp % 2 == 1){
res = (res * b) % MD;
}
b = (b * b) % MD;
exp /= 2;
}
return res;
};
v.push_back(n);
sort(v.begin(), v.end());
for(int i = 1;i<v.size();i++){
ans = (ans * pw(lf, v[i] - v[i - 1] - 1)) % MD;
--lf;
}
return (int)(ans);
}
