#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]){
vector <pair<int,int>> s;
map <int,int> m;
for (int i = 0; i < n; i++) {
m[inputSeq[i]]++;
if (m[inputSeq[i]] == 2) {return 0;}
if (inputSeq[i] <= n) {
s.push_back({inputSeq[i],i+1});
}
}
int cnt = 0;
for (int i = 1; i < (s).size(); i++) {
if (s[i].first < s[i-1].first) {
cnt++;
if (s[i].first - s[i].second != (s[i-1].first - s[i-1].second)-n) {return 0;}
} else {
if (s[i].first - s[i].second != s[i-1].first - s[i-1].second) {return 0;}
}
}
// cout << cnt << endl;
return (cnt <= 1);
}
int replacement(int n, int a[], int ans[])
{
int c[n+5];
iota(c,c+n,1);
int cur = -1;
map <int,int> m;
int mx = -1;
for (int i = 0; i < n; i++) {
if (a[i] <= n) cur = i;
m[a[i]]=i+1;
mx = max(mx,a[i]);
}
if (cur != -1) {
int pos = a[cur];
for (int i = cur; i < n; i++) {
c[i] = pos++;
if (pos > n) pos = 1;
}
for (int i = 0; i < cur; i++) {
c[i] = pos++;
if (pos > n) pos = 1;
}
}
// cout <<"---" << endl;
// for (int i = 0; i < n; i++) {
// cout << c[i] << " ";
// }
// cout << endl;
// for (int i = n+1; i <= mx; i++) {
// cout << m[i] << " ";
// }
// cout << endl;
for (int i= n+1; i <= mx; i++) {
if (m[i]) {
ans[i-n-1] = c[m[i]-1];
c[m[i]-1] = i;
} else {
ans[i-n-1] = c[m[mx]-1];
c[m[mx]-1] = i;
}
}
// for (int i = 0; i < n; i++) {
// cout << c[i] << " ";
// }
// cout << endl;
return mx-n;
}
//----------------------
int countReplacement(int n, int a[])
{
vector <int> v;
long long ans = 1;
for (int i = 0; i < n; i++) {
if (a[i] > n) v.emplace_back(a[i]);
}
if (v.empty()) return 1;
v.emplace_back(n);
sort(v.begin(),v.end());
int mod = 1e9+7;
auto bp = [&](int x, int n) {
long long res = 1;
while (n) {
if (n&1) {
res = (res * x) % mod;
}
x = (x * x) % mod;
n >>= 1;
}
return res;
};
for (int i = 1; i < v.size(); i++) {
ans *= bp(v.size()-i,v[i]-v[i-1]-1);
ans %= mod;
}
return ans;
}
