#include "gondola.h"
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
const int mod=1e9+9;
int valid(int n, int inputSeq[])
{
vector<int> v;
vector<int> id(n+1,0);
set<int> s;
for (int i=0;i<n;++i) {
int cur=inputSeq[i];
if (cur>n) {
if (s.find(cur)!=s.end()) return 0;
s.insert(cur);
continue;
}
v.push_back(cur);
id[cur]=i+1;
}
sort(begin(v),end(v));
if (v.empty()) return 1;
int cur=v.back(),ja=0;
v.pop_back();
while(!v.empty()) {
int prev=v.back();
if (prev==cur) return 0;
int dist=id[prev]<id[cur]?id[cur]-id[prev]:id[cur]+n-id[prev];
if (dist!=cur-prev){
return 0;
}
if (id[prev]>id[cur]) ++ja;
cur=prev;
v.pop_back();
}
return ja<=1;
}
//----------------------
map<int,int> mapSeq(int n, int gondolaSeq[]) {
int exp=-1,idx=-1;
for (int i=0;i<n;++i) {
int el=gondolaSeq[i];
if (el<=n) {
exp=el;
idx=i;
break;
}
}
map<int,int> mp;
if (exp==-1) exp=1,idx=0;
for (int i=0;i<n;++i) {
int el=gondolaSeq[i];
int cu=exp+i-idx;
cu=(cu-1)%n+1;
if (el>n) mp[el]=cu;
}
return mp;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
map<int,int> mp=mapSeq(n,gondolaSeq);
int se=n;
int m=0;
for (auto [i,j]:mp) {
replacementSeq[m++]=j;
++se;
for (se;se<i;++se) {
replacementSeq[m++]=se;
}
}
return m;
}
//----------------------
#define intt long long
intt ppow(intt n,int m) {
n%=mod;
intt res=1;
while(m) {
if (m&1) res*=n,res%=mod;
n*=n;
n%=mod;
m>>=1;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n,inputSeq))return 0;
map<int,int> mp=mapSeq(n,inputSeq);
int cu=n,se=mp.size();
intt res=1;
for (auto [i,j]:mp) {
int cur=i-cu-1;
cu=i;
res*=ppow(se,cur);
res%=mod;
--se;
}
return res;
}
