#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include "gondola.h"
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline T range(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline void setin(string s) {
freopen(s.c_str(), "r", stdin);
}
inline void setout(string s) {
freopen(s.c_str(), "w", stdout);
}
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 9;
const int N = 3e5 + 15;
inline int add(int a, int b) {
a = (a + b) % mod;
return (a + mod) % mod;
}
inline int mt(int a, int b) {
return 1ll * a * b % mod;
}
inline int binpow(int n, int k) {
int res = 1;
while(k) {
if(k & 1)
res = mt(res, n);
n = mt(n, n);
k >>= 1;
}
return res;
}
int a[N], b[N];
int valid(int n, int inputSeq[]) {
map <int, int> cnt = {};
for(int i = 0; i < n; ++i) {
a[i] = inputSeq[i] - 1;
if(cnt[a[i]])
return 0;
++cnt[a[i]];
}
for(int i = 0; i < n; ++i) {
if(a[i] < n) {
int cnt = a[i];
for(int j = i; j < n; ++j, cnt = (cnt + 1) % n)
b[j] = cnt;
for(int j = 0; j < i; ++j, cnt = (cnt + 1) % n)
b[j] = cnt;
break;
}
}
for(int i = 0; i < n; ++i)
if(a[i] < n && b[i] < n && a[i] != b[i])
return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for(int i = 0; i < n; ++i)
b[i] = i;
for(int i = 0; i < n; ++i)
a[i] = gondolaSeq[i] - 1;
int cnt = n - 1;
for(int i = 0; i < n; ++i) {
if(a[i] < n) {
int cnt = a[i];
for(int j = i; j < n; ++j, cnt = (cnt + 1) % n)
b[j] = cnt;
for(int j = 0; j < i; ++j, cnt = (cnt + 1) % n)
b[j] = cnt;
break;
}
}
vector <pii> now = {};
for(int i = 0; i < n; ++i)
if(a[i] >= n)
now.pb({a[i], i});
sort(now.begin(), now.end());
int sz = 0;
for(int k = 0; k < now.size(); ++k) {
int val = now[k].f, i = now[k].se;
int &cur = b[i];
while(cnt < val) {
replacementSeq[sz++] = cur + 1;
cur = ++cnt;
}
}
return sz;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq))
return 0;
for(int i = 0; i < n; ++i)
a[i] = inputSeq[i] - 1;
vector <int> now = {};
for(int i = 0; i < n; ++i)
if(a[i] >= n)
now.pb(a[i]);
now.pb(n-1);
sort(now.begin(), now.end());
int res = 1;
for(int i = 1; i < now.size(); ++i)
res = mt(res, binpow(now.size() - i, now[i] - now[i-1] - 1));
if(now.size() == n + 1) {
res = mt(res, n);
}
return res;
}
