#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 9;
long long binaryExpo(long long a, long long b){
long long ans = 1;
while(b > 0){
if(b % 2 == 1){
ans = (ans * a) % MOD;
b--;
}
a = (a * a) % MOD;
b /= 2;
}
return ans;
}
int valid(int n, int inputSeq[]){
vector<int> seq(n);
vector<int> seq2(2 * n);
bool allGreat = true;
set<int> s;
for(int i = 0; i < n; i++){
seq[i] = inputSeq[i];
s.insert(seq[i]);
if(seq[i] <= n){
allGreat = false;
}
}
if((int)s.size() != n){
return 0;
}
for(int i = 0; i < n; i++){
seq2[i + n] = seq[i];
seq2[i] = seq[i];
}
if(allGreat){
return 1;
}
else{
bool works = true;
for(int i = 0; i < n; i++){
if(seq[i] <= n){
int idx = 0;
for(int j = 0; j < n; j++){
if(seq2[j + seq[i] - 1] == seq[i]){
idx = j;
break;
}
}
for(int x = idx; x < idx + n; x++){
if(seq2[x] <= n && seq2[x] != x - idx + 1){
works = false;
break;
}
}
break;
}
}
return (int)works;
}
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
if(!valid(n, gondolaSeq)){
return 0;
}
vector<int> seq(n);
vector<int> seq2(2 * n);
bool allGreat = true;
for(int i = 0; i < n; i++){
seq[i] = gondolaSeq[i];
if(seq[i] <= n){
allGreat = false;
}
}
for(int i = 0; i < n; i++){
seq2[i + n] = seq[i];
seq2[i] = seq[i];
}
if(allGreat){
vector<pair<int, int> > v;
for(int i = 0; i < n; i++){
if(seq[i] > n){
v.push_back(make_pair(seq[i], i + 1));
}
}
sort(v.begin(), v.end());
int idx = 0;
int prev = n;
for(int i = 0; i < (int)v.size(); i++){
replacementSeq[idx++] = v[i].second;
prev++;
for(int j = prev; j < v[i].first; j++){
replacementSeq[idx++] = prev;
prev++;
}
}
return idx;
}
for(int i = 0; i < n; i++){
if(seq[i] <= n){
int idx = 0;
for(int j = 0; j < n; j++){
if(seq2[j + seq[i] - 1] == seq[i]){
idx = j;
break;
}
}
vector<pair<int, int> > v;
for(int i = idx; i < idx + n; i++){
if(seq2[i] > n){
v.push_back(make_pair(seq2[i], i - idx + 1));
}
}
sort(v.begin(), v.end());
int idx2 = 0;
int prev = n;
for(int i = 0; i < (int)v.size(); i++){
replacementSeq[idx2++] = v[i].second;
prev++;
for(int j = prev; j < v[i].first; j++){
replacementSeq[idx2++] = prev;
prev++;
}
}
return idx2;
}
}
return 0;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)){
return 0;
}
vector<int> seq(n);
vector<int> seq2(2 * n);
bool allGreat = true;
for(int i = 0; i < n; i++){
seq[i] = inputSeq[i];
if(seq[i] <= n){
allGreat = false;
}
}
for(int i = 0; i < n; i++){
seq2[i + n] = seq[i];
seq2[i] = seq[i];
}
if(allGreat){
vector<long long> v;
int mxVal = 0;
for(int i = 0; i < n; i++){
if(seq[i] > n){
v.push_back(seq[i]);
mxVal = max(mxVal, seq[i]);
}
}
v.push_back(n);
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
long long ans = 1;
for(int i = 0; i < (int)v.size() - 1; i++){
ans = (ans * binaryExpo((i + 1), v[i] - v[i + 1] - 1)) % MOD;
}
ans = (ans * n) % MOD;
return ans;
}
for(int i = 0; i < n; i++){
if(seq[i] <= n){
int idx = 0;
for(int j = 0; j < n; j++){
if(seq2[j + seq[i] - 1] == seq[i]){
idx = j;
break;
}
}
vector<long long> v;
int mxVal = 0;
for(int i = idx; i < idx + n; i++){
if(seq2[i] > n){
v.push_back(seq2[i]);
mxVal = max(mxVal, seq2[i]);
}
}
v.push_back(n);
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
long long ans = 1;
for(int i = 0; i < (int)v.size() - 1; i++){
ans = (ans * binaryExpo((i + 1), v[i] - v[i + 1] - 1)) % MOD;
}
return ans;
}
}
return 0;
}
// int main(){
// // cout << binaryExpo(2, 10) << "\n";
// int n;
// cin >> n;
// int gondolaSeq[n];
// for(int i = 0; i < n; i++){
// cin >> gondolaSeq[i];
// }
// cout << countReplacement(n, gondolaSeq) << "\n";
// }
