#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int valid(int n, int inputSeq[])
{
set<int> st;
for (int i=0; i<n; i++)
{
if (st.find(inputSeq[i])!=st.end()) return 0;
st.insert(inputSeq[i]);
}
int s, cnt(0);
bool can=1;
pair<int, int> mn={INT_MAX, -1};
for (int i=0; i<n; i++) mn=min(mn, {inputSeq[i], i});
if (mn.first>n) return 1;
cnt=mn.first;
s=mn.second;
for (int i=s; i<n; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
for (int i=0; i<s; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
return can;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int cnt(0), res(0);
set<pair<int, int>> s;
for (int i=0; i<n; i++) if (gondolaSeq[i]>n) s.insert({gondolaSeq[i], i});
pair<int, int> mn={INT_MAX, -1};
for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) mn=min(mn, {gondolaSeq[i], i});
if (mn.first==INT_MAX) mn={1, 0};
cnt=mn.first-1;
vector<int> p(n);
for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
for (auto [x, y]:s)
{
replacementSeq[res++]=p[y];
while (res+n!=x) replacementSeq[res]=res+n, res++;
}
return res;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
int cnt(0), sz(n+1), l(0);
long long ans=1;
set<pair<int, int>> s;
for (int i=0; i<n; i++) if (inputSeq[i]>n) s.insert({inputSeq[i], i});
pair<int, int> mn={INT_MAX, -1};
for (int i=0; i<n; i++) if (inputSeq[i]<=n) mn=min(mn, {inputSeq[i], i});
if (mn.first==INT_MAX) mn={1, 0};
cnt=mn.first-1;
vector<int> p(n);
for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
l=s.size();
for (auto [x, y]:s)
{
while (sz!=x) ans=(ans*l)%mod, sz++;
sz++;
l--;
//cout<<x<<' '<<y<<' '<<ans<<' '<<l<<'\n';
}
return ans;
}
