#include "gondola.h"
#include <assert.h>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
bool visited[250003];
int rotos[250003];
bool rangos[250003];
struct dato{
int valor;
int pos;
};
bool operator <(const dato &a, const dato &b){
return a.valor < b.valor;
}
dato gon[250003];
int valid(int n, int inputSeq[])
{
int index = 0, aux, valor = 1;
for (int i = 0; i < n; i++){
aux = inputSeq[i];
if (aux <= n){
index = i;
valor = aux;
break;
}
}
for (int i = index; i < n + index; i++){
if (visited[ inputSeq[i % n] ]) return 0;
visited[ inputSeq[i % n] ] = true;
if (inputSeq[i % n] > n){
valor = (valor % n) + 1;
continue;
}
if (inputSeq[i % n] != valor) return 0;
valor = (valor % n) + 1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int index = 0, aux, valor = 1, L = 0, g = n + 1;
for (int i = 0; i < n; i++){
aux = gondolaSeq[i];
if (aux <= n){
index = i;
valor = aux;
break;
}
}
int posi = 0;
for (int i = index; i < n + index; i++){
aux = gondolaSeq[i % n];
if (aux > n ){
gon[posi].valor = aux;
gon[posi].pos = valor;
posi++;
}
valor = (valor % n) + 1;
}
sort (gon + 0, gon + posi);
g = n + 1;
for (int i = 0; i < posi; i++){
if (gon[i].valor <= n) continue;
replacementSeq[L] = gon[i].pos;
L++;
while (g < gon[i].valor){
replacementSeq[L] = g;
g++;
L++;
}
g = gon[i].valor + 1;
}
return L;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
long long res = 1, maxi = 0, r = 0;
bool uwu = false;
if (!valid(n, inputSeq)) return 0;
for (int i = 0; i < n; i++){
if (inputSeq[i] > n){
r++;
if (inputSeq[i] > maxi) maxi = inputSeq[i];
rangos[inputSeq[i]] = true;
}
}
if (r == n) uwu = true;
if (r == 0) return 1;
long long int mod = 1000000009;
for (int i = n + 1; i <= maxi; i++){
if (rangos[i]) r--;
else res = res * r % mod;
}
if (uwu) res = res * n % mod;
return res;
}
