#include "gondola.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
bool is_unique(int n, int arr[]){
set<int> s;
for (int i = 0; i < n; i++){
if (s.count(arr[i]))
return false;
s.insert(arr[i]);
}
return true;
}
vector<int> beginning(int n, int pos, int value){
vector<int> arr(n);
for (int i = 0; i < n; i++){
arr[pos] = value+1;
pos = (pos+1)%n;
value = (value+1)%n;
}
return arr;
}
int valid(int n, int arr[]){
if (!is_unique(n, arr))
return false;
int pos = -1;
for (int i = 0; i < n; i++)
if (arr[i] <= n)
pos = i;
if (pos == -1)
return 1;
vector<int> original = beginning(n, pos, arr[pos]-1);
for (int i = 0; i < n; i++)
if (arr[i] <= n and arr[i] != original[i])
return 0;
return 1;
}
//----------------------
int replacement(int n, int arr[], int answer[]){
assert(valid(n, arr));
int max_value = 0, pos = -1;
int min_value = INT_MAX;
for (int i = 0; i < n; i++){
max_value = max(max_value, arr[i]);
min_value = min(min_value, arr[i]);
if (arr[i] <= n)
pos = i;
}
if (max_value <= n)
return 0;
vector<int> original(n);
for (int i = 0; i < n; i++)
original[i] = i+1;
if (min_value <= n)
original = beginning(n, pos, arr[pos]-1);
vector<int> idx;
for (int i = 0; i < n; i++)
if (arr[i] > n)
idx.push_back(i);
sort(idx.begin(), idx.end(), [&](int x, int y){
return (arr[x] < arr[y]);
});
int position = 0, last = n+1;
for (int i = 0; i < int(idx.size()); i++){
answer[position++] = original[idx[i]];
while (last < arr[idx[i]])
answer[position++] = last++;
last += 1;
}
return position;
}
//----------------------
const int MOD = 1e9+9;
int mod(ll x){
return (x%MOD);
}
int Fe(int x, int y){
if(!y)
return 1;
int h = Fe(x, y/2);
h = mod(h*1LL*h);
if (y&1)
h = mod(h*1LL*x);
return h;
}
int countReplacement(int n, int arr[]){
if (!valid(n, arr))
return 0;
vector<int> idx;
for (int i = 0; i < n; i++)
if (arr[i] > n)
idx.push_back(i);
sort(idx.begin(), idx.end(), [&](int x, int y){
return (arr[x] < arr[y]);
});
int free_n = int(idx.size()), ans = 1, last = n;
if (free_n == n)
ans = n;
for (int i = 0; i < int(idx.size()); i++){
int cur = arr[idx[i]];
ans = mod(ans * 1LL * Fe(free_n, cur - last - 1));
last = cur;
free_n -= 1;
}
return ans;
}
