#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
using ii = pair<int, int>;
const int MAX = 250069;
const int mod = 1e9 + 9;
template<int MOD = mod>
struct Mint
{
int val;
Mint() : val(0) {}
Mint(int64_t _val) : val((int)(_val % MOD)) { if (val < 0) val += MOD; }
Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }
friend Mint fpow(Mint x, int64_t y)
{
Mint res = 1;
for (; y > 0; y >>= 1, x *= x)
{
if (y & 1)
res *= x;
}
return res;
}
friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }
friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
friend Mint operator- (Mint a) { return 0 - a; }
friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
};
int valid(int n, int inputSeq[])
{
bitset<MAX> vst;
for (int i = 0; i < n; ++i)
{
if (vst[inputSeq[i]])
return 0;
vst[inputSeq[i]] = true;
}
int pos = -1;
for (int i = 0; i < n; ++i) if (inputSeq[i] <= n)
{
int tmp = (inputSeq[i] - i + n) % n;
if (pos == -1) pos = tmp;
if (pos != tmp) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ar[MAX];
{
int pos = 0;
for (int i = 1; i < n; ++i)
if (gondolaSeq[i] < gondolaSeq[pos])
pos = i;
if (gondolaSeq[pos] <= n)
pos = (pos - gondolaSeq[pos] + 1 + n) % n;
else pos = 0;
iota(ar+pos, ar+n, 1);
iota(ar, ar+pos, n-pos+1);
}
vector<ii> v;
for (int i = 0; i < n; ++i)
v.pb({gondolaSeq[i], i});
sort(v.begin(), v.end());
int sz = 0, cur = n+1;
for (auto &[x, pos] : v)
{
while (ar[pos] != x)
{
replacementSeq[sz++] = ar[pos];
ar[pos] = cur++;
}
}
return sz;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
int ar[MAX];
{
int pos = 0;
for (int i = 1; i < n; ++i)
if (inputSeq[i] < inputSeq[pos])
pos = i;
if (inputSeq[pos] <= n)
pos = (pos - inputSeq[pos] + 1 + n) % n;
else pos = 0;
iota(ar+pos, ar+n, 1);
iota(ar, ar+pos, n-pos+1);
}
vector<ii> v;
for (int i = 0; i < n; ++i)
v.pb({inputSeq[i], i});
sort(v.begin(), v.end());
Mint<> res = 1;
int cur = n+1, rem = 0;
for (int i = 0; i < n; ++i)
rem += inputSeq[i] != ar[i];
for (auto &[x, pos] : v)
{
while (ar[pos] != x)
{
if (x == cur) rem--;
else res *= rem;
ar[pos] = cur++;
}
}
return res.val;
}
