#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
int valid(int n, int inputSeq[])
{
int s = -1;
bitset<250001> ud;
for(int i=0; i<n; i++) {
if(inputSeq[i] <= n) {
s = i;
}
if(ud[inputSeq[i]]) {
// cout << " :: " << inputSeq[i] << endl;
return 0;
}
// cout << "ud[" << inputSeq[i] << "] = 1\n";
ud[inputSeq[i]] = 1;
}
if(s != -1) {
int val = inputSeq[s]-1;
s--;
for(int i=0; i<n; i++) {
s = (s+1)%n;
val = ((val) % n) + 1;
cerr << inputSeq[s] << " " << val << endl;
if(inputSeq[s] <= n && inputSeq[s] != val) return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int l = 0;
vector<pair<int,int>> gseq;
vector<int> rseq;
for(int i=0; i<n; i++) {
gseq.push_back({gondolaSeq[i], i});
}
gseq.pb({n, n});
sort(gseq.begin(), gseq.end(), greater<pii>());
int t = 0;
for(int i = 0; i<n && gseq[i].fi > n; i++) {
//cout << i << " " << gseq[i].fi << endl;
t = gseq[i].fi - gseq[i+1].fi;
while(t--) rseq.pb(gseq[i].se);
}
int s = 0;
for(int i = 0; i<n; i++) {
if(gondolaSeq[i] <= n) {
s = gondolaSeq[i] - i - 1;
break;
}
}
l = rseq.size();
reverse(rseq.begin(), rseq.end());
for(int i=0; i<l; i++) {
replacementSeq[i] = ((rseq[i] + s + n) % n) + 1;
//cerr << replacementSeq[i] << " ";
}
//cerr << "\n";
return l;
}
//----------------------
const int m = 1e9+9;
ll mul (ll a, ll b) {
return (a*b) % m;
}
ll binpow(ll a, ll b) {
ll ret = 1;
while(b) {
if(b&1) ret = mul(a, ret);
a = mul(a, a);
b >>= 1;
}
return ret;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
int maxi = 0;
vector<pii> v;
for(int i=0; i<n; i++) {
v.push_back({inputSeq[i], i});
maxi = max(maxi, inputSeq[i]);
}
if(maxi == n) return 1;
v.push_back({n, n});
ll ans = 1;
sort(v.begin(), v.end(), greater<pii> ());
for(int i=0; i<n && v[i].fi > n; i++) {
ll dif = v[i].fi - v[i+1].fi;
ans = mul(ans, binpow(i+1, dif-1));
}
return ans;
}
