#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e6 + 100, M = 1e7 + 10, len = 21, inf = 1e18;
const ll mod = 1000000009LL;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll um(ll a, ll b){
return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
bool cc[N];
int valid(int n, int arr[])
{
int cur = 0;
bool was = false;
for(int i = 0; i < 2 * n; i++){
cur = cur%n + 1;
if(i < n){
if(cc[arr[i%n]] == true) return 0;
cc[arr[i%n]] = true;
}
if(was){
if(arr[i%n] > n) continue;
if(arr[i%n] != cur) return 0;
} else{
if(arr[i%n] <= n){
was = true;
cur = arr[i%n];
}
}
}
return 1;
}
//----------------------
int replacement(int n, int arr[], int res[])
{
int cur = 0;
bool was = false;
vector <pii> vec;
for(int i = 0; i < 2 * n; i++){
cur = cur%n + 1;
if(was == false && arr[i%n] <= n){
was = true;
cur = arr[i%n];
}
if(was == true){
if(cc[cur]) continue;
cc[cur] = true;
vec.pb({arr[i%n], cur});
}
}
if(was == false){
for(int i = 0; i < n; i++){
vec.pb({arr[i], i + 1});
}
}
sort(vec.begin(), vec.end());
int from = 0, lt;
bool mk = false;
for(int i = 0; i < (int)vec.size(); i++){
if(vec[i].F == vec[i].S) continue;
res[from++] = vec[i].S;
if(mk == false) lt = n + 1;
else lt = vec[i - 1].F + 1;
for(int j = lt; j < vec[i].F; j++){
res[from++] = j;
}
mk = true;
}
return from;
}
//----------------------
int countReplacement(int n, int arr[])
{
int rs = valid(n, arr);
if(rs == 0) return 0;
int cur = 0, mx = 0;
ll ans = 1, cnt = 0;
bool was = false;
vector <pii> vec;
for(int i = 0; i < 2 * n; i++){
cur = cur%n + 1;
mx = max(mx, arr[i % n]);
if(was == false && arr[i%n] <= n){
was = true;
cur = arr[i%n];
}
if(was == true){
if(cc[cur]) continue;
cc[cur] = true;
vec.pb({arr[i%n], cur});
}
}
if(was == false){
for(int i = 0; i < n; i++){
vec.pb({arr[i], i + 1});
}
ans = n;
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for(int i = 0; i < (int)vec.size(); i++){
if(vec[i].F == vec[i].S) continue;
cnt++;
}
for(int i = n + 1; i <= mx; i++){
if((int)vec.size() > 0){
if(vec.back().F == i){
cnt--;
vec.pop_back();
continue;
}
}
ans = um(ans, cnt);
}
return ans;
}
