#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
#include "gondola.h"
int valid(int n, int arr[]){
int x = -1;
set<int> S;
for(int i = 0; i < n; i++) S.insert(arr[i]);
if(sz(S) != n) return 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n){
x = i;
break;
}
}
if(x == -1) return 1;
for(int i = 0; i < n; i++){
if(arr[(x + i) % n] <= n && arr[(x + i) % n] != (arr[x] + i - 1) % n + 1) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int arr[], int ans[]){
vector<int> A(n);
for(int i = 0; i < n; i++) A[i] = arr[i];
map<int, int> S;
for(int i = 0; i < n; i++) S[A[i]] = i;
int x = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n){
x = i;
break;
}
}
for(int i = 0; i < n; i++){
arr[(x + i) % n] = (arr[x] + i - 1) % n + 1;
}
int X = max_element(all(A)) - A.begin();
for(int i = n + 1; i <= A[X]; i++){
if(S.count(i)) ans[i - n - 1] = arr[S[i]], arr[S[i]] = i;
else ans[i - n - 1] = arr[X], arr[X] = i;
}
return A[X] - n;
}
//----------------------
int countReplacement(int n, int arr[]){
if(!valid(n, arr)) return 0;
int ans = 1;
vector<int> A(n);
for(int i = 0; i < n; i++) A[i] = arr[i];
map<int, int> S;
for(int i = 0; i < n; i++) if(A[i] > n) S[A[i]] = i;
int X = max_element(all(A)) - A.begin();
for(int i = n + 1; i <= A[X]; i++){
if(S.count(i)){
S.erase(i);
}
else{
ans = 1ll * ans * sz(S) % 1000000009;
}
}
return ans;
}
