#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 1;
const int MOD = 1e9 + 9;
const int MAX_N = 1e5;
int lgput(int a, int n) {
if (n == 0)
return 1;
int p = lgput(a, n / 2);
p = (long long)p * p % MOD;
if (n % 2 == 1)
p = (long long)p * a % MOD;
return p;
}
map<int, int> frecv;
int valid(int n, int inputSeq[]) {
int pos = 0, minn = INF + 1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < minn) {
minn = inputSeq[i];
pos = i;
}
}
int a = minn;
int i = pos;
do {
if (inputSeq[i] <= n) {
if (inputSeq[i] != a)
return false;
} else {
if (frecv[inputSeq[i]])
return false;
frecv[inputSeq[i]]++;
}
a = a % n + 1;
i = (i + 1) % n;
} while (i != pos);
return true;
}
//----------------------
int realVal[MAX_N];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int pos = 0, minn = INF + 1;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] < minn) {
minn = gondolaSeq[i];
pos = i;
}
}
int a = min(n, minn);
int i = pos;
vector<pair<int, int>> v;
do {
realVal[i] = a;
a = a % n + 1;
if (gondolaSeq[i] > n)
v.push_back({gondolaSeq[i], i});
i = (i + 1) % n;
} while (i != pos);
int rep = n;
sort(v.begin(), v.end());
int l = 0;
for (auto p: v) {
replacementSeq[l++] = realVal[p.second];
rep++;
while (rep < p.first) {
replacementSeq[l++] = rep;
rep++;
}
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
int pos = 0, minn = INF + 1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < minn) {
minn = inputSeq[i];
pos = i;
}
}
int a = min(n, minn);
int i = pos;
vector<pair<int, int>> v;
do {
realVal[i] = a;
if (inputSeq[i] <= n) {
if (inputSeq[i] != a)
return false;
} else {
if (frecv[inputSeq[i]])
return false;
frecv[inputSeq[i]]++;
}
a = a % n + 1;
if (inputSeq[i] > n)
v.push_back({inputSeq[i], i});
i = (i + 1) % n;
} while (i != pos);
int rep = n;
sort(v.begin(), v.end());
int all = v.size();
int ans = 1;
for (auto p: v) {
int lib = p.first - rep - 1;
rep = p.first;
ans = (long long)ans * lgput(all, lib) % MOD;
all--;
}
if (n < minn) {
ans = (long long)ans * n % MOD;
}
return ans;
}
