#pragma GCC optimize ("O3")
#include "gondola.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int valid(int n, int inputSeq[]) {
set<int>s(inputSeq, inputSeq + n);
if (size(s) < n) return 0;
int shift = -1;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
if (shift == -1) shift = (inputSeq[i] - (i + 1) + n) % n;
else if ((inputSeq[i] - (i + 1) + n) % n != shift) {
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int shift = 0;
vector<pii>rep;
for (int i = 0; i < n; ++i) {
if (gondolaSeq[i] <= n) {
shift = (gondolaSeq[i] - (i + 1) + n) % n;
break;
}
}
for (int i = 0; i < n; ++i) {
if (gondolaSeq[i] > n) {
rep.eb(mpr(gondolaSeq[i], (i + shift) % n + 1));
}
}
rep.eb(mpr(n, n));
int ptr = 0;
sort(all(rep), greater<pii>());
int sz = size(rep);
for (int i = 0; i < sz - 1; ++i) {
for (int j = rep[i].f - 1; j > rep[i + 1].f; --j) {
replacementSeq[ptr++] = j;
}
replacementSeq[ptr++] = rep[i].s;
}
reverse(replacementSeq, replacementSeq + ptr);
return ptr;
}
//----------------------
const int mod = 1e9 + 9;
int binPow(int a, int n) {
if (n == 0) return 1;
if ((n & 1)) return (1ll * a * binPow(a, n - 1)) % mod;
else return binPow((1ll * a * a) % mod, n / 2);
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) return 0;
vector<int>rep;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] > n) {
rep.eb(inputSeq[i]);
}
}
rep.eb(n);
sort(all(rep), greater<int>());
int sz = size(rep);
int res = 1;
for (int i = 1; i < sz; ++i) {
res = (1ll * res * binPow(i, rep[i - 1] - rep[i] - 1)) % mod;
}
if (sz == n + 1) {
res = (1ll * n * res) % mod;
}
return res;
}
