#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
const ll MOD = 1e9 + 9;
void shift_inputSeq(int n, int inputSeq[], int shiftby)
{
for (int i = 0; i < n; ++i)
inputSeq[i] += shiftby;
}
int valid(int n, int inputSeq[])
{
shift_inputSeq(n, inputSeq, -1);
int shift2fix = -1;
for (int i = 0; i < n; ++i)
{
if (inputSeq[i] < n)
{
int shift = (n + i - inputSeq[i]) % n;
if (shift2fix == -1)
shift2fix = shift;
else if (shift2fix != shift)
return 0;
}
}
sort(inputSeq, inputSeq + n);
for (int i = 0; i < n - 1; ++i)
if (inputSeq[i] == inputSeq[i + 1])
return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
shift_inputSeq(n, gondolaSeq, -1);
int shift2fix = -1;
for (int i = 0; i < n; ++i)
{
if (gondolaSeq[i] < n)
{
int shift = (n + i - gondolaSeq[i]) % n;
if (shift2fix == -1)
shift2fix = shift;
else if (shift2fix != shift)
assert(false);
}
}
if (shift2fix == -1)
shift2fix = 0;
vpii replaced;
for (int i = 0; i < n; ++i)
{
int idx = (shift2fix + i) % n;
if (gondolaSeq[idx] != i)
{
assert(gondolaSeq[idx] > i);
replaced.push_back({gondolaSeq[idx], i});
}
}
sort(replaced.begin(), replaced.end());
int m = n; // current gondola to place
for (int i = 0; i < sz(replaced); ++i)
{
int to_replace = replaced[i].second;
assert(m <= replaced[i].first);
while (m <= replaced[i].first)
{
replacementSeq[m - n] = to_replace;
to_replace = m;
++m;
}
}
int final_size = m - n;
shift_inputSeq(final_size, replacementSeq, +1);
return final_size;
}
ll fastexp(ll base, ll exp)
{
if (exp == 0)
return 1;
ll tmp = fastexp(base, exp / 2);
ll res = (exp % 2 == 1) ? base : 1;
res = (((res * tmp) % MOD) * tmp) % MOD;
return res;
}
//----------------------
int foobar[100001];
int countReplacement(int n, int inputSeq[])
{
copy(inputSeq, inputSeq + n, foobar);
if (!valid(n, foobar))
return 0; // needed because of multiple same numbers later...
// return 1 if no gondola broke down
shift_inputSeq(n, inputSeq, -1);
int shift2fix = -1;
for (int i = 0; i < n; ++i)
{
if (inputSeq[i] < n)
{
int shift = (n + i - inputSeq[i]) % n;
if (shift2fix == -1)
shift2fix = shift;
else if (shift2fix != shift)
assert(false);
}
}
ll factor = 1;
if (shift2fix == -1)
shift2fix = 0, factor = n;
vpii replaced;
for (int i = 0; i < n; ++i)
{
int idx = (shift2fix + i) % n;
if (inputSeq[idx] != i)
{
assert(inputSeq[idx] > i);
replaced.push_back({inputSeq[idx], i});
}
}
ll res = 1;
sort(replaced.begin(), replaced.end());
int m = n; // current gondola to place
for (int i = 0; i < sz(replaced); ++i)
{
assert(m <= replaced[i].first);
res = (res * fastexp(sz(replaced) - i, replaced[i].first - m)) % MOD;
m = replaced[i].first + 1;
}
res = (res * factor) % MOD;
return res;
}
