#include <iostream>
#include <algorithm>
#include <map>
#include <gondola.h>
using namespace std;
const int mod = 1e9 + 9;
int input[100000];
map<int, bool> has;
int original[100001];
int index[250001];
int use_for_replacement[100000];
long long binary_exponentiation(int a, int b){
if (b == 0){
return 1;
}
long long cache = binary_exponentiation(a, b/2);
long long ans = (cache * cache) % mod;
if (b % 2 == 1){
ans = (ans * a) % mod;
}
return ans;
}
int valid(int n, int inputSeq[]){
for (int i = 0;i < n;i++){
if (has[inputSeq[i]]){
return 0;
}
has[inputSeq[i]] = true;
}
int first_original = -1;
for (int i = 0;i < n;i++){
if (inputSeq[i] <= n){
first_original = i;
break;
}
}
if (first_original == -1){
return 1;
}
for (int i = 0;i < n;i++){
if (inputSeq[i] <= n){
int diff1 = i - first_original;
int diff2 = inputSeq[i] - inputSeq[first_original];
if (diff2 < 0){
diff2 += n;
}
if (diff1 != diff2){
return 0;
}
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int has_index = -1;
int max_num = -1;
for (int i = 0;i < n;i++){
if (gondolaSeq[i] <= n){
has_index = i;
}
max_num = max(max_num, gondolaSeq[i]);
index[gondolaSeq[i]] = i;
}
if (has_index == -1){
for (int i = 0;i < n;i++){
original[i] = i + 1;
}
}
else{
int first = gondolaSeq[has_index] - has_index;
if (first < 0){
first += n;
}
for (int i = 0;i < n;i++){
original[i] = (first + i) % n;
if (original[i] == 0){
original[i] = n;
}
}
}
int length = 0;
for (int i = n + 1;i <= max_num;i++){
if (index[i] != 0 or gondolaSeq[0] == i){
replacementSeq[length] = original[index[i]];
length++;
original[index[i]] = i;
}
else{
replacementSeq[length] = original[index[max_num]];
length++;
original[index[max_num]] = i;
}
}
return length;
}
int countReplacement(int n, int inputSeq[]){
if (valid(n, inputSeq) == 0){
return 0;
}
sort(inputSeq, inputSeq + n);
if (inputSeq[n - 1] == n){
return 1;
}
int first_greater_n = -1;
for (int i = 0;i < n;i++){
if (inputSeq[i] > n){
first_greater_n = i;
break;
}
}
long long ans = binary_exponentiation(n - first_greater_n, (inputSeq[first_greater_n] - 1) - n);
ans %= mod;
for (int i = first_greater_n;i < (n - 1);i++){
ans *= binary_exponentiation(n - (i + 1), (inputSeq[i + 1] - 1) - inputSeq[i]);
ans %= mod;
}
if (inputSeq[0] > n){
ans *= n;
ans %= mod;
}
return ans;
}
