#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int inputSeq[]){
vector<int> a;
int mn = 1e6;
set<int> val;
for (int i = 0; i < n; i++){
mn = min(mn, inputSeq[i]);
val.insert(inputSeq[i]);
}
for (int i = 0; i < n; i++){
if (inputSeq[i] == mn) a.push_back(mn);
else if (!a.empty()){
a.push_back(inputSeq[i]);
}
}
for (int i = 0; i < n; i++){
if (inputSeq[i] == mn) break;
a.push_back(inputSeq[i]);
}
int cnt = a[0];
int f = 1;
for (int i = 0; i < n; i++){
if (cnt == a[i] || a[i] >= n + 1) {
cnt++;
continue;
}
f = 0;
}
if ((int)(val.size()) != n) f = 0;
return f;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vector<int> a;
int mn = 1e6;
for (int i = 0; i < n; i++){
mn = min(mn, gondolaSeq[i]);
}
for (int i = 0; i < n; i++){
if (gondolaSeq[i] == mn) a.push_back(mn);
else if (!a.empty()){
a.push_back(gondolaSeq[i]);
}
}
for (int i = 0; i < n; i++){
if (gondolaSeq[i] == mn) break;
a.push_back(gondolaSeq[i]);
}
int cnt = a[0];
if (a[0] >= n + 1) cnt = 1;
set<pair<int, int>> repla;
for (int i = 0; i < n; i++){
if (cnt == n + 1) cnt = 1;
if (cnt == a[i]) {
cnt++;
continue;
}else{
repla.insert({a[i], cnt});
cnt++;
}
}
int l = 0;
int cur = n + 1;
for (auto x : repla){
//cout << x.first << ' ' << x.second << endl;
replacementSeq[l] = x.second;
l++;
while(cur < x.first){
replacementSeq[l] = cur;
l++;
cur++;
}
cur++;
}
return l;
}
const long long MOD = 1e9 + 9;
long long binpow(long long a, long long b){
if(!b) return 1;
else if(b % 2 == 0){
long long x = binpow(a, b / 2);
return (x * x) % MOD;
}else{
long long x = binpow(a, b / 2);
x = (x * x) % MOD;
return (x * a) % MOD;
}
}
int countReplacement(int n, int inputSeq[]){
vector<long long> a;
int mn = 1e9;
for (int i = 0; i < n; i++){
mn = min(mn, inputSeq[i]);
}
for (int i = 0; i < n; i++){
if (inputSeq[i] == mn) a.push_back(mn);
else if (!a.empty()){
a.push_back(inputSeq[i]);
}
}
for (int i = 0; i < n; i++){
if (inputSeq[i] == mn) break;
a.push_back(inputSeq[i]);
}
long long cnt = a[0];
long long ans = 1;
if (a[0] >= n + 1) {
cnt = 1;
ans *= n;
}
if (valid(n, inputSeq) == 0){
return 0;
}
set<pair<long long, long long>> repla;
for (int i = 0; i < n; i++){
if (cnt == n + 1) cnt = 1;
if (cnt == a[i]) {
cnt++;
continue;
}else{
repla.insert({a[i], cnt});
cnt++;
}
}
long long tama = repla.size();
long long cur = n + 1;
tama %= MOD;
for (auto x : repla){
long long d = x.first - cur;
ans *= (binpow(tama, d) % MOD);
ans %= MOD;
cur = x.first + 1;
tama--;
}
return ans;
}
