#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int ar[])
{
map<int,int>mp;
vector<int>v;
int cnt=0;
int mx=0;
for(int i=0;i<n;i++){
mp[ar[i]]++;
mx=max(mx,ar[i]);
if(ar[i]<=n)v.push_back(ar[i]);
cnt+=(mp[ar[i]]>1?2:0);
}
//cerr<<"cnt:"<<cnt<<"\n";
int st=0;
int mn=n+1;
for(int i=0;i<n;i++){
if(ar[i]<mn){
mn=ar[i];
st=i;
}
}
//cerr<<"mn:"<<mn<<" "<<st<<"\n";
if(mn<=n){
int cur=mn;
for(int i=0;i<n;i++){
int id=(i+st)%n;
if(ar[id]<=n){
if(ar[id]!=cur)cnt+=2;
}
cur++;
}
}
//cerr<<"cnt:"<<cnt<<"\n";
//for(int i=n+1;i<=mx;i++)if(mp[i]==0)cnt+=2;
//cerr<<"cnt:"<<cnt<<"\n";
return cnt<=1;
}
//----------------------
int replacement(int n, int ar[], int rans[])
{
map<int,int>mp;
vector<int>v;
int cnt=0;
int mx=0;
for(int i=0;i<n;i++){
mp[ar[i]]=i+1;
mx=max(mx,ar[i]);
}
//cerr<<"mp[92]:"<<mp[92]<<"\n";
//cerr<<"cnt:"<<cnt<<"\n";
int st=0;
int mn=n+1;
for(int i=0;i<n;i++){
if(ar[i]<mn){
mn=ar[i];
st=i;
}
}
//cerr<<"mn:"<<mn<<" "<<st<<"\n";
vector<int>val(n+5);
multiset<int>ms;
for(int i=0;i<n;i++)ms.insert(i);
queue<int>q;
int cur=mn;
for(int i=0;i<n;i++){
int id=(i+st)%n;
if(cur<=n){
if(ar[id]<=n){
if(ar[id]==cur){
ms.erase(id);
//cerr<<"have:"<<cur<<" "<<i<<"\n";
}
}
}
val[id]=(cur>n?cur-n:cur);
cur++;
}
if(mn>n){
for(int i=0;i<n;i++)val[i]=i+1;
}
cur=n;
/*cerr<<"info:\n";
for(int i=0;i<n;i++)cerr<<val[i]<<" ";
cerr<<"\n";
for(auto x:ms)cerr<<x<<"\n";
cerr<<"end\n";*/
vector<int>ans;
int ii=0;
for(int i=1;i<=mx-n;i++){
cur++;
if(mp[cur]==0){
int x=*ms.begin();
ans.push_back(val[x]);
rans[ii]=val[x];
ii++;
val[x]=cur;
}else{
int x=val[mp[cur]-1];
//cerr<<"gopos:"<<mp[cur]-1<<" "<<x<<"\n";
ans.push_back(x);
rans[ii]=x;
ii++;
val[mp[cur]-1]=cur;
ms.erase(mp[cur]-1);
}
}
//for(int i=0;i<n;i++)cerr<<val[i]<<" ";
//cerr<<"\n";
for(int i=0;i<n;i++){
assert(val[i]==ar[i]);
}
return ans.size();
}
//----------------------
long long md=1e9+7;
int countReplacement(int n, int ar[])
{
if(!valid(n,ar))return 0;
//cerr<<"pass\n";
long long ans=1;
map<int,int>mp;
vector<int>v;
int cnt=0;
int mx=0;
for(int i=0;i<n;i++){
mp[ar[i]]=i+1;
mx=max(mx,ar[i]);
}
//cerr<<"mp[92]:"<<mp[92]<<"\n";
//cerr<<"cnt:"<<cnt<<"\n";
int st=0;
int mn=n+1;
for(int i=0;i<n;i++){
if(ar[i]<mn){
mn=ar[i];
st=i;
}
}
//cerr<<"mn:"<<mn<<" "<<st<<"\n";
vector<int>val(n+5);
multiset<int>ms;
for(int i=0;i<n;i++)ms.insert(i);
queue<int>q;
int cur=mn;
for(int i=0;i<n;i++){
int id=(i+st)%n;
if(cur<=n){
if(ar[id]<=n){
if(ar[id]==cur){
ms.erase(id);
//cerr<<"have:"<<cur<<" "<<i<<"\n";
}
}
}
val[id]=(cur>n?cur-n:cur);
cur++;
}
if(mn>n){
for(int i=0;i<n;i++)val[i]=i+1;
ans=n;
}
cur=n;
/*cerr<<"info:\n";
for(int i=0;i<n;i++)cerr<<val[i]<<" ";
cerr<<"\n";
for(auto x:ms)cerr<<x<<"\n";
cerr<<"end\n";*/
int ii=0;
for(int i=n+1;i<=mx;i++){
if(mp[i]==0){
int x=*ms.begin();
long long sz=ms.size();
ans=(ans*sz)%md;
//ans%=md;
//cerr<<sz<<" "<<ans<<"\n";
ii++;
val[x]=cur;
}else{
int x=val[mp[i]-1];
//cerr<<"gopos:"<<mp[cur]-1<<" "<<x<<"\n";
ii++;
if(x==i)continue;
val[mp[i]-1]=i;
ms.erase(mp[i]-1);
}
}
//for(int i=0;i<n;i++)cerr<<val[i]<<" ";
//cerr<<"\n";
//cerr<<(ans*3)%md<<"\n";
return ans;
}
