#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll m = 1000000009;
int valid(int n, int inputSeq[]){
vector<ll> v(n);
ll ssf = (ll) pow(10, 10);
int si;
unordered_set<int> us;
for (int i=0; i<n; i++){
if (us.find(inputSeq[i]) != us.end()) return 0;
us.insert(inputSeq[i]);
if (inputSeq[i] < ssf){
ssf = inputSeq[i];
si = i;
}
}
if (ssf > n) return 1;
for (int i=0; i<n; i++){
v[(ssf+i-1)%n] = inputSeq[(si+i)%n];
if (v[(ssf+i-1)%n] <= n && v[(ssf+i-1)%n] != i+1) return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vector<ll> v(n);
ll ssf = (ll) pow(10, 10);
int si;
for (int i=0; i<n; i++){
if (gondolaSeq[i] < ssf){
ssf = gondolaSeq[i];
si = i;
}
}
if (ssf > n){
ssf = 1;
si = 0;
}
priority_queue<pair<int,int>> pq;
for (int i=0; i<n; i++){
v[(ssf+i-1)%n] = gondolaSeq[(si+i)%n];
if (v[(ssf+i-1)%n] > n) pq.push({-v[(ssf+i-1)%n], (ssf+i-1)%n});
}
int cur = n+1;
while (!pq.empty()){
int x = -pq.top().first, i = pq.top().second;
pq.pop();
bool nw = true;
while (cur <= x){
if (nw) replacementSeq[cur-n-1] = i+1;
else replacementSeq[cur-n-1] = cur-1;
nw = false;
cur++;
}
}
return cur-n-1;
}
ll power(ll a, ll b){
if (b == 0) return 1;
if (b == 1) return a;
ll res = power(a, b/2);
res = ((ll)res*(ll)res)%m;
if (b % 2) return (a*res) % m;
return res;
}
int countReplacement(int n, int inputSeq[]){
if (!valid(n, inputSeq)) return 0;
ll res = 1, r = 0, cur = n;
priority_queue<ll> pq;
for (int i=0; i<n; i++){
if (inputSeq[i] > n){
r++;
pq.push(-inputSeq[i]);
}
}
if (r == n) res = n;
while (!pq.empty()){
ll next = -pq.top();
pq.pop();
res = (res*power(r, next-cur-1)) % m;
cur = next;
r--;
}
return res;
}
