#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int MOD = 1000000009;
int valid(int n, int inputSeq[]) {
int fixed = -1;
vector<int> aux(MAX_N, 0);
for(int i = 0; i < n; ++i)
if(inputSeq[i] <= n)
fixed = i;
for(int i = 0; i < n; ++i)
aux[i] = inputSeq[i];
sort(aux.begin(), aux.begin() + n);
for(int i = 0; i < n - 1; ++i) // All gondolas must be distinct
if(aux[i] == aux[i + 1])
return false;
if(fixed == -1) // All gondolas have been replaced
return true;
for(int i = 0; i < n; ++i) {
int expected = (inputSeq[fixed] + i - 1) % n + 1;
int expectedPos = (fixed + i) % n;
if(!(inputSeq[expectedPos] == expected || inputSeq[expectedPos] > n))
return false;
}
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int top = 0, lastVal = n;
int fixed = -1;
vector<pair<int, int> > aux;
for(int i = 0; i < n; ++i) {
if(gondolaSeq[i] > n)
aux.push_back(make_pair(gondolaSeq[i], i));
else
fixed = i;
}
sort(aux.begin(), aux.end());
for(auto it: aux) {
int expectedVal;
if(fixed != -1)
expectedVal = (gondolaSeq[fixed] + it.second - fixed + 2 * n - 1) % n + 1;
else
expectedVal = it.second + 1;
replacementSeq[top++] = expectedVal;
++lastVal;
while(lastVal < it.first) {
replacementSeq[top++] = lastVal;
lastVal++;
}
}
return top;
}
//----------------------
int lgputm(int a, int b) {
int ac = 1;
while(b > 0) {
if(b % 2 == 1)
ac = (long long)ac * a % MOD;
a = (long long)a * a % MOD;
b /= 2;
}
return ac;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) // ayyyy lmao
return 0;
int rez = 1, rem, lastVal = n, fixed = -1;
vector<int> aux;
for(int i = 0; i < n; ++i)
if(inputSeq[i] > n)
aux.push_back(inputSeq[i]);
else
fixed = i;
sort(aux.begin(), aux.end());
rem = aux.size();
for(auto it: aux) {
rez = (long long)rez * lgputm(rem, it - lastVal - 1) % MOD;
lastVal = it;
rem--;
}
if(fixed == -1)
rez = (long long) rez * n % MOD;
return rez;
}
