#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int mini = n + 10, id = 0;
map<int, bool> marc;
for(int i = 0; i < n; i++){
if(marc[inputSeq[i]]) return 0;
if(inputSeq[i] < mini) mini = inputSeq[i], id = i;
marc[inputSeq[i]] = 1;
}
if(mini >= n) return 1;
for(int i = 0; i < n; i++){
if(inputSeq[(id + i) % n] <= n && inputSeq[(id + i) % n] != mini) return 0;
mini++;
if(mini > n) mini = 1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
map<int, int> ini;
int mini = 250001, id = 0;
vector<pair<int, int> > ord;
for(int i = 0; i < n; i++){
ord.push_back(make_pair(gondolaSeq[i], i));
if(gondolaSeq[i] < mini) mini = gondolaSeq[i], id = i;
}
if(mini > n) mini = 1, id = 0;
for(int i = 0; i < n; i++){
ini[(i + id) % n] = mini;
mini++;
if(mini > n) mini = 1;
}
int cnt = 0;
int removeNow = n + 1;
sort(ord.begin(), ord.end());
for(int i = 0; i < n; i++){
if(ord[i].first <= n) continue;
replacementSeq[cnt++] = ini[ord[i].second];
while(removeNow != ord[i].first)
replacementSeq[cnt++] = removeNow++;
removeNow++;
}
return cnt;
}
//----------------------
const long long MOD = 1e9 + 9;
long long fexp(long long val, long long a){
if(a == 0) return 1;
if(a == 1) return val;
long long ret = fexp(val, a / 2);
ret *= ret;
ret %= MOD;
if(a % 2 == 1) ret *= val, ret %= MOD;
return ret;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
long long ret = 1;
long long alive = n;
int cur = n + 1;
vector<pair<int, int> > ord;
for(int i = 0; i < n; i++)
ord.push_back(make_pair(inputSeq[i], i));
sort(ord.begin(), ord.end());
bool flag = true;
for(int i = 0; i < n; i++){
if(ord[i].first <= n){
flag = false;
alive--;
continue;
}
long long val = ord[i].first - cur;
ret *= fexp(alive, val);
ret %= MOD;
cur = ord[i].first + 1;
alive--;
}
if(flag) ret *= n, ret %= MOD;
return ret;
}
