#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int mod = 1e9+9;
int valid(int n, int inputSeq[])
{
deque<int> a(n);
deque<int> perm(n);
for (int i = 0; i<n; i++) {
perm[i] = i;
a[i] = inputSeq[i]-1;
}
for (int i=0; i<=n; i++) {
if (a==perm) return 1;
perm.push_back(perm[0]);
perm.pop_front();
}
return 0;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int start = -1;
for (int i = 0; i<n; i++) {
gondolaSeq[i]--;
if (gondolaSeq[i] < n) {
if (start == -1)
start = (n+i-gondolaSeq[i])%n;
assert(start == (n+i-gondolaSeq[i])%n);
}
}
if (start == -1) start = 0;
set<pair<int, int>> replacements;
set<int> okToReplace;
for (int i = start; i<n+start; i++) {
if (gondolaSeq[i%n] != i-start) {
replacements.insert({gondolaSeq[i%n], i-start});
okToReplace.insert(i-start);
}
}
int curr = n;
map<int, int> dict;
for (int i: okToReplace) {
dict[i]=i;
}
while (replacements.size()) {
assert((*replacements.begin()).first >= curr);
assert(okToReplace.size());
if ((*replacements.begin()).first == curr) {
replacementSeq[curr-n] = dict[(*replacements.begin()).second]+1;
okToReplace.erase((*replacements.begin()).second);
replacements.erase(replacements.begin());
}
else {
replacementSeq[curr-n] = dict[*okToReplace.begin()]+1;
dict[*okToReplace.begin()] = curr;
}
curr++;
}
return curr-n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int start = -1;
for (int i = 0; i<n; i++) {
inputSeq[i]--;
if (inputSeq[i] < n) {
if (start == -1)
start = (n+i-inputSeq[i])%n;
if (start != (n+i-inputSeq[i])%n) return 0;
}
}
set<pair<int, int>> replacements;
set<int> okToReplace;
for (int i = start; i<n+start; i++) {
if (inputSeq[i%n] != i-start) {
replacements.insert({inputSeq[i%n], i-start});
okToReplace.insert(i-start);
}
}
int curr = n;
long int res = 1;
while (replacements.size()) {
if (!okToReplace.size()) return 0;
if ((*replacements.begin()).first < curr) return 0;
if ((*replacements.begin()).first == curr) {
// replacementSeq[curr-n] = (*replacements.begin()).second+1;
okToReplace.erase((*replacements.begin()).second);
replacements.erase(replacements.begin());
}
else {
// replacementSeq[curr-n] = *okToReplace.begin()+1;
res *= okToReplace.size();
res %= mod;
okToReplace.erase(okToReplace.begin());
okToReplace.insert(curr);
}
curr++;
}
return res;
}
