#include <vector>
#include <algorithm>
#include "gondola.h"
int valid(int n, int inputSeq[]) {
int cat = 0;
for (int i = 0; i < n; i++)
if (inputSeq[i] <= n)
cat = inputSeq[i] - i - 1;
if (cat < 0)
cat += n;
for (int i = 0; i < n; i++)
if (inputSeq[i] <= n && cat != inputSeq[i] - i - 1 && cat != inputSeq[i] - i - 1 + n)
return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int cat = 0;
std::vector < std::pair < int, int > > q;
for (int i = 0; i < n; i++)
if (gondolaSeq[i] <= n)
cat = gondolaSeq[i] - i - 1;
else
q.push_back({gondolaSeq[i], i});
if (cat < 0)
cat += n;
int e = n + 1, ans = 0;
std::sort(q.begin(), q.end());
for (auto &x : q) {
replacementSeq[ans++] = (x.second + cat) % n + 1;
while (e < x.first) {
replacementSeq[ans++] = e;
e++;
}
e++;
}
return ans;
}
//----------------------
#define MOD 1000000009
inline int lgput(int a, int n) {
int r = 1;
while (n) {
if (n % 2)
r = 1LL * r * a % MOD;
a = 1LL * a * a % MOD;
n /= 2;
}
return r;
}
int countReplacement(int n, int inputSeq[]) {
if (valid(n, inputSeq) == 0)
return 0;
std::vector < int > r(1, n);
for (int i = 0; i < n; i++)
if (inputSeq[i] > n)
r.push_back(inputSeq[i]);
std::sort(r.begin(), r.end());
int ans = 1;
for (int i = 1; i < (int)r.size(); i++)
ans = 1LL * ans * lgput(r.size() - i, r[i] - r[i - 1] - 1);
return ans;
}
