#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j , k) for(int i = j; i < (int) k; i++)
typedef vector<int> vi;
const int N = 3e5 + 10;
int pos[N];
map<int , int> mp;
int valid(int n, int A[])
{
mp.clear();
rep(i , 0 , n) {
if (mp.count(A[i])) return 0;
mp[A[i]] = i;
}
int last = -1;
rep(i , 1 , n + 1)
if(mp.count(i)) {
if (!~last) {
last = i;
continue;
}
if ((i - last) != (mp[i] - mp[last] + n) % n)
return 0;
}
return 1;
}
//----------------------
int lo[N];
set<int> st;
int replacement(int n, int A[], int B[])
{
st.clear();
memset(pos , -1, sizeof(pos));
int mx = -1;
rep(i , 0 , n) {
pos[A[i]] = i;
mx = max(mx , A[i]);
}
bool flag = false;
rep(i , 1 , n + 1)
if (~pos[i]) {
rep(j , 1 , n + 1) {
lo[(pos[i] + j - i + n) % n] = j;
if(!~pos[j])
st.insert((pos[i] + j - i + n) % n);
}
flag = true;
break;
}
if (!flag)
rep(i , 1 , n + 1) {
lo[i - 1] = i;
st.insert(i - 1);
}
int L = 0;
rep(i , n + 1, mx + 1) {
if (~pos[i]) {
B[L++] = lo[pos[i]];
st.erase(pos[i]);
}
else {
int v = *st.begin();
B[L++] = lo[v];
lo[v] = i;
}
}
return L;
}
//----------------------
const int MOD = 1e9 + 9;
typedef long long ll;
ll po(ll a , ll b) { return b ? po(a * a % MOD, b >> 1) * (b & 1 ? a : 1) % MOD : 1; }
int countReplacement(int n, int A[])
{
if(!valid(n , A)) return 0;
ll res = 1;
int cnt = n;
int last = -1;
while (!mp.empty() && mp.begin()->first <= n) {
cnt--;
last = mp.begin()->first;
mp.erase(mp.begin());
}
if(last == -1) res = n;
last = n;
int pp;
while(!mp.empty()) {
int me = mp.begin()->first;
assert(me - last - 1 >= 0);
res = (res * po(cnt , me - last - 1)) % MOD;
last = me;
cnt--;
pp = mp.size();
mp.erase(mp.begin());
assert(pp != mp.size());
}
return res;
}
