//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define sp << " " <<
#define nl << "\n"
#define ll long long
int valid(int n, int a[]){
ll least = n+1, ind = -1;
map<ll, ll> m;
for(ll i=0; i<n; ++i){
if(a[i] < least) least = a[i], ind = i;
if(m[a[i]]) return 0;
++m[a[i]];
}
if(least<=n){
for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n){
if(a[i]<=n and a[i]!=ii+least) return 0;
}
}
return 1;
}
int replacement(int n, int inp[], int* ans){
ll least = n+1, ind = 0;
for(ll i=0; i<n; ++i){
if(inp[i] < least) least = inp[i], ind = i;
}
if(least>n) least = 1;
ll inp0[n];
for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n) inp0[i] = ii+least;
vector<pair<ll, ll>> b;
for(ll i=0; i<n; ++i) b.emplace_back(inp[i], i);
sort(b.begin(), b.end());
vector<vector<ll>> a(n);
ll toPut = 0, extra = n+1;
for(auto ii : b){
ll i = ii.second;
if(inp[i]>n){
ans[toPut++] = inp0[i];
for(ll j=extra; j<inp[i]; ++j){
ans[toPut++] = j;
}
extra = inp[i] + 1;
}
}
return toPut;
}
ll modExpo(ll x, ll p){
ll m = 1e9 + 9;
ll res = 1, toMul = x % m;
while(p){
if(p&1){
res = (res * toMul) % m;
}
toMul = (toMul * toMul) % m;
p /= 2;
}
return res;
}
int countReplacement(int n, int inp[]){
const ll MOD = 1e9 + 9;
if(!valid(n, inp)) return 0;
ll res = 1;
ll least = n+1, ind = 0;
for(ll i=0; i<n; ++i){
if(inp[i] < least) least = inp[i], ind = i;
}
if(least>n) least = 1, res = n;
ll inp0[n];
for(ll ii=0, i=ind; ii<n; ++ii, i=(i+1)%n) inp0[i] = ii+least;
vector<pair<ll, ll>> b;
for(ll i=0; i<n; ++i) b.emplace_back(inp[i], i);
sort(b.begin(), b.end());
vector<vector<ll>> a(n);
ll extra = n+1, left = 0;
for(ll i=0; i<n; ++i) left += (inp[i]>n);
for(auto ii : b){
ll i = ii.second;
if(inp[i]<=n) continue;
ll possible = inp[i] - extra;
res = (res*modExpo(left, possible));
if(res >= MOD) res -= MOD;
--left;
extra = inp[i] + 1;
}
return res;
}
