#include "gondola.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define ll long long int
using namespace std;
const ll M=1e9+7;
int valid(int n, int inputSeq[]){
set<int> seen;
for(int i = 0; i < n; i++){
if(seen.count(inputSeq[i])) return 0;
seen.insert(inputSeq[i]);
}
int pos = -1, st;
for(int i = 0; i < n; i++) if(inputSeq[i] <= n) pos = i, st = inputSeq[i];
if(pos == -1) return 1;
for(int j = 0; j < n; j++, pos++, pos %= n){
if(inputSeq[pos] > n) continue;
if(inputSeq[pos] != (st+j-1)%n+1) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int v[], int R[])
{
int pos1=0;
for(int i=0;i<n;i++){
if(v[i]<=n){
int B=v[i]-1;
if(i-B>=0){
pos1=i-B;
}else{
B-=i;
pos1=n-B;
}
break;
}
}
int pos=pos1;
vector<pair<int,int> >E;//gondola final y gondola inicial
for(int i=1;i<=n;i++){
E.pb({v[pos],i});
pos++;
if(pos==n)pos=0;
}
sort(E.begin(),E.end());
int next=n+1;
int res=0;
for(int i=0;i<n;i++){
if(E[i].F==E[i].S)continue;
R[res]=E[i].S;next++;res++;
//cout<<"pongo "<<E[i].S<<endl;
int curr=next-1;
while(curr!=E[i].F){
//cout<<"pongo "<<curr<<endl;
R[res]=curr;
curr++;next++;res++;
}
}
//cout<<"respuesta "<<res<<endl;
//cout<<endl;
return res;
}
//----------------------
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
vector<int> a(250001);
ll s = 1, m = n;
for(int i = 0; i < n; i++) a[inputSeq[i]]++;
for(int i = 249999; i > n; i--) a[i] += a[i+1];
for(int i = n+1; i < 250000; i++){
if(!a[i]) break;
if(a[i] == a[i+1]) s *= a[i], s %= M;
}
for(int i = 0; i < n; i++) if(inputSeq[i] <= n) m = 1;
s *= m, s %= M;
return s;
}
//number of subtask
//n
//3 1 4
//5 1 2 3 4
//2 3 4 9 6 7 1
