#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
set<int> s;
for (int i = 0; i < n; i++) {
s.insert(inputSeq[i]);
}
if ((int)s.size() != n) {
return 0;
}
int off = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
off = (i + n - inputSeq[i] + 1) % n;
break;
}
}
if (off != -1) {
for (int i = 0; i < n; i++) {
if (inputSeq[(i + off) % n] <= n && inputSeq[(i + off) % n] != i + 1) {
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int off = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n) {
off = (i + n - gondolaSeq[i] + 1) % n;
break;
}
}
vector<pair<int, int>> last;
for (int i = 0; i < n; i++) {
if (gondolaSeq[(i + off) % n] != i + 1) {
last.emplace_back(gondolaSeq[(i + off) % n], i + 1);
}
}
if (last.empty()) {
return 0;
}
sort(last.begin(), last.end());
int sz = last.size();
int prv = last.back().second;
for (int i = 0; i < sz; i++) {
for (int j = (i > 0 ? last[i - 1].first + 1 : n + 1); j < last[i].first; j++) {
replacementSeq[j - n - 1] = prv;
prv = j;
}
replacementSeq[last[i].first - n - 1] = (i < sz - 1 ? last[i].second : prv);
}
return last[sz - 1].first - n;
}
//----------------------
const long long mod = 1e9 + 9;
long long bin_pow(long long x, int y) {
long long res = 1;
while (y) {
if (y & 1) {
res = res * x % mod;
}
y >>= 1;
x = x * x % mod;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
set<int> s;
for (int i = 0; i < n; i++) {
s.insert(inputSeq[i]);
}
if ((int)s.size() != n) {
return 0;
}
int off = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
off = (i + n - inputSeq[i] + 1) % n;
break;
}
}
if (off != -1) {
for (int i = 0; i < n; i++) {
if (inputSeq[(i + off) % n] <= n && inputSeq[(i + off) % n] != i + 1) {
return 0;
}
}
}
vector<int> last;
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) {
last.push_back(inputSeq[i]);
}
}
sort(last.begin(), last.end());
int sz = last.size();
long long res = 1;
for (int i = 0; i < sz; i++) {
res = res * bin_pow(sz - i, last[i] - (i > 0 ? last[i - 1] : n) - 1) % mod;
}
if (off == -1) {
res = res * n % mod;
}
return res;
}
