#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
using ll = long long;
const int INF = numeric_limits<int>::max() / 2;
int valid(int n, int inputSeq[])
{
int minv = INF;
int index = -1;
for (int i = 0; i < n; ++i)
{
if (inputSeq[i] <= 0)
{
return 0;
}
if (inputSeq[i] <= n)
{
minv = inputSeq[i] - i;
index = i;
break;
}
}
for (int i = index + 1; i < n; ++i)
{
if (inputSeq[i] <= 0)
{
return 0;
}
if (inputSeq[i] <= n)
{
if (inputSeq[i]%n != (minv + i)%n)
{
return 0;
}
}
}
sort(inputSeq,inputSeq+n);
int last = -1;
for (int i = 0; i < n; ++i)
{
if (inputSeq[i] == last) {
return 0;
}
last = inputSeq[i];
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int minv = 1;
int index = -1;
int l = 0;
map<int,int> m{};
for (int i = 0; i < n; ++i)
{
m[gondolaSeq[i]] = i;
// if (gondolaSeq[i] <= n)
// {
// minv = gondolaSeq[i] - i;
// index = i;
// break;
// }
}
for (auto p : m) {
if (p.first <= n) {
minv = (p.first - p.second + n)%n;
}
break;
}
int rep = n+1;
for (auto p : m) {
if (p.first <= n) {
continue;
}
int r = (minv + p.second + n)%n;
if (r==0) {
r = n;
}
while (r < p.first) {
replacementSeq[l] = r;
++l;
r = rep;
++rep;
}
}
return l;
}
//----------------------
int M = 1000000009;
ll exp(ll a, ll b) {
if (b==0) {
return 1;
}
if (b==1) {
return a;
}
ll half = exp(a,b/2);
if (b%2==0){
return (half*half)%M;
}
else {
return (((half*half)%M)*a)%M;
}
}
int countReplacement(int n, int inputSeq[])
{
if (!(valid(n,inputSeq))) {
return 0;
}
int minv = 1;
int index = -1;
int l = 0;
map<int,int> m{};
for (int i = 0; i < n; ++i)
{
m[inputSeq[i]] = i;
// if (gondolaSeq[i] <= n)
// {
// minv = gondolaSeq[i] - i;
// index = i;
// break;
// }
}
ll out = 1;
for (auto p : m) {
if (p.first <= n) {
minv = (p.first - p.second + n)%n;
break;
}
out=n;
break;
}
ll last = n;
ll broken = n;
for (auto p : m) {
if (p.first <= n) {
--broken;
continue;
}
out = (out * exp(broken,(p.first-last-1)))%M;
last = p.first;
--broken;
}
return out;
}
