#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input freopen("in.txt","r", stdin)
#define print_output freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 3e5+10;
int next(int p, int n) {
int ret = (p + 1) % n;
return (ret == 0)? n : ret;
}
int prev(int p, int n) {
if(p == 0) return n-1;
else return p-1;
}
int valid(int n, int inputSeq[])
{
set<int> s;
for(int i = 0; i < n; i++) s.insert(inputSeq[i]);
if(s.size() != n) return 0;
vector<pii> v;
for(int i = 0; i < n; i++) {
if(inputSeq[i] <= n) v.pb({inputSeq[i], i});
}
if(v.empty()) return 1;
sort(v.begin(), v.end());
for(int i = 0; i < v.size() - 1; i++) {
int del = v[i+1].first - v[i].first;
int del2 = v[i+1].second - v[i].second;
if(del2 < 0) del2 += n;
if(del != del2) return 0;
}
return 1;
}
//----------------------
int pos[maxn];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
memset(pos, -1, sizeof pos);
vector<int> v, dummy, target(n);
int mx = 0, none = 1;
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] > n) {
dummy.pb(i);
pos[gondolaSeq[i]] = i;
mx = max(mx, gondolaSeq[i]);
}
else none = 0;
}
for(int i = 0; i < n; i++) target[i] = gondolaSeq[i];
if(!none) {
for(int i = 0; i < n; i++) {
if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
}
for(int i = 0; i < n; i++) {
if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
}
}
else {
for(int i = 0; i < n; i++) gondolaSeq[i] = i+1;
}
for(int i = n+1, d = 0; i <= mx; i++) {
if(pos[i] == -1) {
while(gondolaSeq[dummy[d]] == target[dummy[d]]) d++;
v.pb(gondolaSeq[dummy[d]]), gondolaSeq[dummy[d]] = i;
}
else v.pb(gondolaSeq[pos[i]]), gondolaSeq[pos[i]] = i;
}
int idx = 0;
for(auto i : v) replacementSeq[idx++] = i;
return v.size();
}
//----------------------
const int mod = 1e9+9;
ll bigmod(ll a, ll b) {
if(b == 0) return 1;
ll x = bigmod(a, b/2);
x = (x * x) % mod;
if(b & 1) x = (x * a) % mod;
return x;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
vector<int> v;
for(int i = 0; i < n; i++) v.pb(inputSeq[i]);
sort(v.begin(), v.end(), greater<int>());
ll ret = 1;
if(v[n-1] > n) {
for(int i = n; i >= 1; i--) ret = (ret * i) % mod, v.pb(i);
}
for(int i = 1; i < v.size(); i++) {
ll q = 0;
if(v[i] < n+1) {
if(v[i-1] == n+1) break;
q = v[i-1] - n - 1;
ret = (ret * bigmod(i, q)) % mod;
break;
}
else {
q = v[i-1] - v[i] - 1;
}
ret = (ret * bigmod(i, q)) % mod;
}
return ret;
}
