#include "gondola.h"
//#include "grader.cpp"
#include <set>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 5;
namespace Valid
{
bool seen[MAXN];
bool sortedL[MAXN], sortedR[MAXN];
void fillSeen(int n, int a[], int maxVal)
{
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
seen[ a[i] ] = true;
}
}
bool check(int n, int a[], int relevant)
{
int maxVal = 0;
for(int i = 0;i<n;i++)
{
maxVal = max(maxVal, a[i]);
sortedL[i] = sortedR[i] = false;
}
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
if(seen[ a[i] ]==true) return false;
seen[ a[i] ] = true;
}
sortedL[0] = true;
int lastRelevant = -1;
for(int i = 1;i<n;i++)
{
if(a[i]>relevant) sortedL[i] = sortedL[i-1];
else sortedL[i] = (sortedL[i-1]&(lastRelevant<a[i])), lastRelevant = a[i];
}
lastRelevant = MAXN;
sortedR[n-1] = true;
for(int i = n-2;i>=0;i--)
{
if(a[i]>relevant) sortedR[i] = sortedR[i+1];
else sortedR[i] = (sortedR[i+1]&(a[i]<lastRelevant)), lastRelevant = a[i];
}
if(sortedL[n-1]==true && (a[n-1]==n || (a[n-1]>relevant && seen[n]==false))) return true;
for(int i = 0;i<n-1;i++)
{
if(sortedL[i]==true && sortedR[i+1]==true)
{
if(a[i]>relevant || a[i+1]>relevant)
{
if(((a[i]>relevant && seen[n]==false) || a[i]==n) &&
((a[i+1]>relevant && seen[1]==false) || a[i+1]==1))
{
return true;
}
}
else
{
if(a[i]==n && a[i+1]==1)
{
return true;
}
}
}
}
return false;
}
};
namespace Replacement
{
bool checkSpecial(int n, int a[])
{
for(int i = 0;i<n;i++)
{
if(a[i]<=n) return false;
}
return true;
}
vector <pair <int, int>> genRaw(int n, int a[])
{
int shift = -1;
for(int i = 0;i<n;i++)
{
if(a[i]<=n)
{
if(a[i]<=i+1) shift = (i + 1) - a[i];
else shift = (n - a[i]) + (i + 1);
break;
}
}
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
if(a[i]>n)
{
out.push_back({a[i], (i-shift+n)%n+1});
}
}
return out;
}
vector <pair <int, int>> genRawSpecial(int n, int a[])
{
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
out.push_back({a[i], i+1});
}
return out;
}
vector <int> solve(int n, int a[])
{
vector <int> answer;
vector <pair <int, int>> raw;
if(checkSpecial(n, a)==false) raw = genRaw(n, a);
else raw = genRawSpecial(n, a);
int num = n + 1;
sort(raw.begin(), raw.end());
for(pair <int, int> x: raw)
{
if(num!=x.first)
{
answer.push_back(x.second);
num++;
while(num<=x.first)
{
answer.push_back(num-1);
num++;
}
}
else
{
answer.push_back(x.second);
num++;
}
}
return answer;
}
};
namespace CountReplacements
{
const long long mod = 1e9 + 9;
long long fastPow(long long x, long long p)
{
long long ans = 1, curr = x;
while(p!=0)
{
if(p%2!=0) ans = (ans*curr)%mod;
p/=2;
curr = (curr*curr)%mod;
}
return ans;
}
long long inv(long long x)
{
return fastPow(x, mod-2);
}
long long solve(vector <pair <int, int>> &raw, int n)
{
int num = n + 1;
long long answer = 1;
for(pair <int, int> x: raw)
{
while(num<x.first)
{
int cnt = 0;
for(pair <int, int> y: raw)
{
if(y.second<num && num<y.first) cnt++;
}
answer = (answer*cnt)%mod;
num++;
}
if(num==x.first)
{
num++;
continue;
}
}
return answer;
}
};
int valid(int n, int inputSeq[])
{
return Valid::check(n, inputSeq, n);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> v = Replacement::solve(n, gondolaSeq);
for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];
return v.size();
}
int countReplacement(int n, int inputSeq[])
{
if(Valid::check(n, inputSeq, n)==false) return 0;
vector <pair <int, int>> raw;
if(Replacement::checkSpecial(n, inputSeq)==false) raw = Replacement::genRaw(n, inputSeq);
else raw = Replacement::genRawSpecial(n, inputSeq);
sort(raw.begin(), raw.end());
long long answer = CountReplacements::solve(raw, n);
if(Replacement::checkSpecial(n, inputSeq)==true) answer = (answer*n)%CountReplacements::mod;
return answer;
}
