#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MAXV = 250000;
const int MAXN = 100000;
const int MOD = 1e9 + 9;
map<int, int> fr;
struct nume {
int valf, vali;
} v2[MAXN];
char cmp(nume a, nume b) {
return a.valf < b.valf;
}
int valid(int n, int v[]) {
int i, p, minr, j, rez;
//trebuie sa nu apara duplicate, fac cu map ca o sa folosesc functia si pentru ultimele subtaskuri
minr = n + 1;
p = -1;
rez = 1;
for (i = 0; i < n; i++) {
if (v[i] < minr) {
minr = v[i];
p = i;
}
if (fr.count(v[i]) > 0) {
rez = 0;
}
fr[v[i]] = 1;
}
if (rez == 0) {//daca sunt duplicate
return 0;
}
if (minr > n) {
return 1;
}
//verific daca restul sunt pe pozitiile corecte
for (i = 1; i < n; i++) {
j = (p + i) % n;
if (v[j] <= n && v[j] != minr + i) {
rez = 0;
}
}
return rez;
}
int replacement(int n, int v[], int rep[]) {
//este corecta secventa
//gasesc la fiecare valoare initiala cat trebuie sa devina
int i, p, minr, j, x, nr;
minr = n + 1;
p = 0;
for (i = 0; i < n; i++) {
if (v[i] < minr) {
minr = v[i];
p = i;
}
}
if (minr == n + 1) {
minr = 1;//consider ca pe prima pozitie este 1
}
nr = 0;
for (i = 0; i < n; i++) {
j = (p + i) % n;
if (v[j] > n) {
v2[nr].valf = v[j];//valoarea finala
v2[nr].vali = (minr + i - 1) % n + 1;//valoarea initiala
nr++;
}
}
sort(v2, v2 + nr, cmp);
j = 0;
x = n + 1;
for (i = 0; i < nr; i++) {
rep[j] = v2[i].vali;
j++;
for (; x < v2[i].valf; x++) {
rep[j] = x;
j++;
}
x = v2[i].valf + 1;
}
return j;
}
int expRapida(int a, int b) {
int rez;
rez = 1;
while (b > 0) {
if (b % 2 > 0) {
rez = (long long)rez * a % MOD;
}
a = (long long)a * a % MOD;
b /= 2;
}
return rez;
}
int countReplacement(int n, int v[]) {
if (valid(n, v) == 0) {
return 0;
}
//este corecta secventa
int i, minr, j, nr, rez;
minr = n + 1;
for (i = 0; i < n; i++) {
if (v[i] < minr) {
minr = v[i];
}
}
rez = 1;
if (minr == n + 1) {
rez = n;//daca toate sunt > n nu stiu cine trebuie sa ajunga la fiecare valoare deci pot fi in orice ordine
//si in total sunt n posibilitati, adica depinde de cine este primul
}
nr = 0;
for (j = 0; j < n; j++) {
if (v[j] > n) {
v2[nr].valf = v[j];//valoarea finala, doar asta conteaza
nr++;
}
}
sort(v2, v2 + nr, cmp);
if (nr > 0) {
rez = (long long)rez * expRapida(nr, v2[0].valf - n - 1) % MOD;
for (i = 1; i < nr; i++) {
rez = (long long)rez * expRapida(nr - i, v2[i].valf - v2[i - 1].valf - 1) % MOD;
}
}
return rez;
}
