#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
bool exist[maxn];
int fin_val[maxn];
ll cnt[maxn];
int valid(int n, int arr[]) {
bool check = true;
for(int i=1;i<n;i++) {
if(arr[i] > n) continue;
else if(arr[i] == 1) {
if(arr[i-1] < n)
check = false;
}
else {
if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
}
}
sort(arr, arr+n);
for(int i=1;i<n;i++) {
if(arr[i] == arr[i-1]) check = false;
}
if(check) return 1;
else return 0;
}
//----------------------
int replacement(int n, int arr[], int replacementSeq[]) {
int maxm = 0;
int found_i = 0, st_val = 1;
for(int i=0;i<n;i++) {
exist[arr[i]] = true;
if(arr[i] <= n) {
found_i = i;
st_val = arr[i];
}
maxm = max(maxm, arr[i]);
}
exist[n] = true;
int l = maxm - n;
for(int i=found_i;i<n;i++) {
fin_val[i] = st_val;
st_val++;
if(st_val == n + 1) st_val = 1;
}
for(int i=0;i<found_i;i++) {
fin_val[i] = st_val;
st_val++;
if(st_val == n + 1) st_val = 1;
}
for(int i=0;i<n;i++) {
while(!exist[arr[i]-1] && arr[i] > n) {
replacementSeq[arr[i]-n-1] = arr[i] - 1;
arr[i]--;
}
if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
}
return l;
}
//----------------------
int countReplacement(int n, int arr[]) {
if(!valid(n, arr)) return 0;
int minv = INT_MAX, maxv = 0;
for(int i=0;i<n;i++) {
minv = min(minv, arr[i]);
maxv = max(maxv, arr[i]);
exist[arr[i]] = true;
}
ll result = 1LL;
for(int i=maxv;i>=n+1;i--) {
cnt[i] = cnt[i+1];
if(exist[i]) cnt[i]++;
}
for(int i=n+1;i<=maxv;i++) {
if(!exist[i]) {
result *= cnt[i];
result %= mod;
}
}
if(minv > n) {
result *= n;
result %= mod;
}
return result;
}
/*int main() {
int arr[] = {2, 3, 4, 12, 6, 7, 1};
int arr2[1];
cout<<countReplacement(7, arr);
}*/
