#include "gondola.h"
#include <bits/stdc++.h>
#define debug(x) std::cout << #x << " = " << x << '\n'
int valid(int n, int inputSeq[])
{
int firstPos = -1;
int correctNumber = 0;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n && firstPos == -1) {
firstPos = i;
correctNumber = inputSeq[i];
}
if (firstPos != -1) {
if (inputSeq[i] <= n && correctNumber != inputSeq[i]) {
return 0;
}
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
}
int bucket[250005];
memset(bucket, 0, sizeof(bucket));
for (int i = 0; i < n; i++) {
if (bucket[inputSeq[i]] == 1)
return 0;
bucket[inputSeq[i]] = 1;
}
return 1;
}
//----------------------
struct gondola {
int actual;
int original;
};
bool byActual(gondola a, gondola b) {
return a.actual < b.actual;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int len = 0;
int firstPos = -1;
int correctNumber = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n && firstPos == -1) {
firstPos = i;
correctNumber = gondolaSeq[i];
break;
}
}
if (firstPos == -1) {
firstPos = 0;
correctNumber = 1;
}
gondola gondolas[n + 3];
for (int i = firstPos; i < n; i++) {
gondolas[i].actual = gondolaSeq[i];
gondolas[i].original = correctNumber;
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
for (int i = 0; i < firstPos; i++) {
gondolas[i].actual = gondolaSeq[i];
gondolas[i].original = correctNumber;
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
std::sort(gondolas, gondolas + n, byActual);
int nextAvailable = n + 1;
for (int i = 0; i < n; i++) {
if (gondolas[i].actual <= n) continue;
replacementSeq[len++] = gondolas[i].original;
while (nextAvailable < gondolas[i].actual) {
replacementSeq[len++] = nextAvailable++;
}
nextAvailable = gondolas[i].actual + 1;
}
return len;
}
//----------------------
typedef long long ll;
#define mod 1000000009
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
bool originalOrder = false;
int maxNumber = 0;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n)
originalOrder = true;
if (inputSeq[i] > maxNumber)
maxNumber = inputSeq[i];
}
ll total = 1;
int idNextGreater = 0;
std::sort(inputSeq, inputSeq + n);
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) {
idNextGreater = i;
break;
}
}
ll availableSpaces = n - idNextGreater + 1;
for (int actGondola = n + 1; actGondola <= maxNumber; actGondola++) {
if (actGondola == inputSeq[idNextGreater]) {
idNextGreater++;
availableSpaces--;
}
else {
total *= availableSpaces;
total %= mod;
}
}
if (originalOrder == false) {
total *= (ll)n;
total %= mod;
}
return total;
}
