#include "gondola.h"
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
using namespace std;
int valid(int n, int inputSeq[])
{
vector<int> a(n);
int d = 0;
for (int i = 0; i < n; ++i) if (inputSeq[i] <= n) d = (i - inputSeq[i] + 1 + n) % n;
for (int i = 0; i < n; ++i) a[(i - d + n) % n] = inputSeq[i] - 1;
if (set<int>(a.begin(), a.end()).size() != n) return 0;
for (int i = 0; i < n; ++i) if (a[i] < n && a[i] != i) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int> a(n);
int d = 0;
for (int i = 0; i < n; ++i) if (gondolaSeq[i] <= n) d = (i - gondolaSeq[i] + 1 + n) % n;
for (int i = 0; i < n; ++i) a[(i - d + n) % n] = gondolaSeq[i];
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0);
sort(inds.begin(), inds.end(), [&a](int l, int r){ return a[l] < a[r]; });
int l = 0, next = n + 1;
for (int i : inds)
{
if (a[i] < next) continue;
replacementSeq[l++] = i + 1;
for (; next < a[i]; ++next) replacementSeq[l++] = next;
++next;
}
return l;
}
//----------------------
using ll = long long;
const ll MOD = 1e9 + 9;
ll binPow(ll a, ll n)
{
ll res = 1;
while (n)
{
if (n & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
n >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0);
sort(inds.begin(), inds.end(), [inputSeq](int l, int r){ return inputSeq[l] < inputSeq[r]; });
ll last = n, counter = n, help = 0;
ll res = 1;
for (int i = 0; i < n; ++i) counter -= inputSeq[i] <= n;
if (counter == n) res = n;
for (int i : inds)
{
if (inputSeq[i] <= n) continue;
ll d = inputSeq[i] - last;
res = (res * binPow(counter, d - 1)) % MOD;
last = inputSeq[i];
--counter;
}
return res;
}
#include <queue>
#include <unordered_map>
unordered_map<int, bool> mark;
const long long md = 1e9 + 9;
long long pw(long long a, long long b){
if(b == 0) return 1ll;
if(b == 1) return a;
long long e = pw(a, b >> 1);
if(b % 2) return ((e * e) % md) * a % md;
return (e * e) % md;
}
int countReplacement2(int n, int inputSeq[])
{
if(valid(n, inputSeq) == 0) return 0;
long long ans = 1, chk = 0;
priority_queue<int, vector<int>, greater<int> > pq;
for(int i = 0; i < n; i++){
if(inputSeq[i] > n) pq.push(inputSeq[i]);
else chk = 1;
}
if(!chk) ans = n * 1ll;
if(pq.empty()) return 1;
pq.push(n);
while(pq.size() > 1){
int u = pq.top(); pq.pop();
int v = pq.top();
ans = (ans * pw(pq.size() * 1ll, (v - u - 1) * 1ll)) % md;
}
return int(ans);
}
