#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define ll long long
unordered_map<int, int> used;
int valid(int n, int inputSeq[]) {
int mn = 1010101010, sv = -1;
for (int i = 0; i < n; i++) {
if (used[inputSeq[i]])return 0;
used[inputSeq[i]] = true;
if (mn > inputSeq[i]) {
mn = inputSeq[i];
sv = i;
}
}
if (mn > n)return 1;
int go = mn;
for (int i = sv - 1; i >= 0; i--) {
go--;
if (go < 1)go += n;
if (inputSeq[i] > n)continue;
if (inputSeq[i] != go)return 0;
}
for (int i = n - 1; i > sv; i--) {
go--;
if (go < 1)go += n;
if (inputSeq[i] > n)continue;
if (inputSeq[i] != go)return 0;
}
return 1;
}
//----------------------
int put[301010];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int mn = 1010101010, sv = -1;
for (int i = 0; i < n; i++) {
if (mn > gondolaSeq[i]) {
mn = gondolaSeq[i];
sv = i;
}
}
int mx = 0;
for (int i = 0; i < n; i++)mx = max(mx, gondolaSeq[i]);
if (mn > n) {
vector<int> use;
for (int i = n + 1; i <= mx; i++)
use.push_back(i);
reverse(use.begin(), use.end());
vector<pair<int, int> > sv;
for (int i = 0; i < n; i++)
sv.push_back({gondolaSeq[i], i});
sort(sv.begin(), sv.end(), [](pair<int, int> q, pair<int, int> w) {
return q.first < w.first;
});
int sz = 0;
for (int i = 0; i < n; i++) {
replacementSeq[sz++] = sv[i].second + 1;
int el = use[use.size() - 1];
use.pop_back();
while (!use.empty() && el != sv[i].first) {
replacementSeq[sz++] = el;
el = use[use.size() - 1];
use.pop_back();
}
}
return sz;
}
vector<int> use;
for (int i = n + 1; i <= mx; i++)
use.push_back(i);
reverse(use.begin(), use.end());
vector<pair<int, int> > SV;
int go = mn;
for (int i = sv - 1; i >= 0; i--) {
go--;
if (go < 1)go += n;
if (gondolaSeq[i] > n){SV.push_back({gondolaSeq[i], go});continue;}
}
for (int i = n - 1; i > sv; i--) {
go--;
if (go < 1)go += n;
if (gondolaSeq[i] > n){SV.push_back({gondolaSeq[i], go});continue;}
}
sort(SV.begin(), SV.end(), [](pair<int, int> q, pair<int, int> w) {
return q.first < w.first;
});
// for (auto [first, second] : SV) {
// cout << first << " " << second << " << " << endl;
// }
int sz = 0;
for (auto [first, second] : SV) {
replacementSeq[sz++] = second;
int el = use[use.size() - 1];
use.pop_back();
while (!use.empty() && el != first) {
replacementSeq[sz++] = el;
el = use[use.size() - 1];
use.pop_back();
}
}
return sz;
}
//----------------------
const ll mod = 1000000009;
ll bp(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)res *= a;
a *= a;
b /= 2;
res %= mod;
a %= mod;
}
return res;
}
ll ans = 1;
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq))return 0;
ll mn = 1010101010, sv = -1;
for (ll i = 0; i < n; i++) {
if (mn > inputSeq[i]) {
mn = inputSeq[i];
sv = i;
}
}
if (mn <= n) {
vector<ll> can = {0};
for (ll i = 0; i < n; i++) {
if (inputSeq[i] > n)
can.push_back(inputSeq[i] - n);
}
sort(can.begin(), can.end());
for (ll i = 1; i < can.size(); i++) {
ans *= bp((ll)(can.size() - i), (ll)(can[i] - can[i - 1] - 1));
ans %= mod;
}
return ans;
} else {
vector<ll> can = {0};
for (ll i = 0; i < n; i++) {
if (inputSeq[i] > n)
can.push_back(inputSeq[i] - n);
}
sort(can.begin(), can.end());
for (ll i = 1; i < can.size(); i++) {
ans *= bp((ll)(can.size() - i), (ll)(can[i] - can[i - 1] - 1));
ans %= mod;
}
ll P = n;
ans *= P;
ans %= mod;
return ans;
}
}
/**
*/
