#include "gondola.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int valid(int n, int inputSeq[]) {
map<int, int>vec; vec.clear();
for (int i = 0; i < n; i++) vec[inputSeq[i]]++;
for (int i = 0; i < n; i++) { if (vec[inputSeq[i]] >= 2) return 0; }
for (int i = 0; i < n; i++) { if (inputSeq[i] > n) inputSeq[i] = -1; }
int v = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] != -1) {
int z = (inputSeq[i] - i + n) % n;
if (v == -1) v = z;
else if (v != z) return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector<int>vec(250009, -1);
int r = -1, maxn = 0;
for (int i = 0; i < n; i++) {
maxn = max(maxn, gondolaSeq[i]); vec[gondolaSeq[i]] = i;
if (gondolaSeq[i] > n) continue;
if (r == -1) r = (gondolaSeq[i] - i + n) % n;
}
if (r == -1) r = 1;
vector<int>vec2(n, 0); for (int i = 0; i < n; i++) vec2[i] = gondolaSeq[i];
for (int i = 0; i < n; i++) { gondolaSeq[i] = (r + i) % n; if (gondolaSeq[i] == 0) gondolaSeq[i] = n; }
int cnt = 0;
for (int i = n + 1; i <= maxn; i++) {
if (vec[i] == -1) {
while (gondolaSeq[cnt] == vec2[cnt]) cnt++;
replacementSeq[i - n - 1] = gondolaSeq[cnt];
gondolaSeq[cnt] = i;
}
else {
replacementSeq[i - n - 1] = gondolaSeq[vec[i]];
gondolaSeq[vec[i]] = i;
}
}
return maxn - n;
}
//----------------------
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 31; i++) {
if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
q *= q; q %= m;
}
return p;
}
int zz[100009];
int countReplacement(int n, int inputSeq[])
{
for (int i = 0; i < n; i++) zz[i] = inputSeq[i];
if (valid(n, zz) == 0) return 0;
bool OK = false;
for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) OK = true; }
long long mod = 1000000009, ret = 1; if (OK == false) ret = n;
sort(inputSeq, inputSeq + n);
int cx = n + 1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] >= cx) {
ret *= modpow(n - i, inputSeq[i] - cx, mod); ret %= mod; cx = inputSeq[i] + 1;
}
}
return ret;
}
