#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
int INF = 1e9;
int mod = 1e9+7;
int exp(int a, int k){
if(k == 0) return 1;
int res = exp(a,k/2);
if(k % 2 == 0){
return (res*res)%mod;
}else{
return ((((res*res)%mod)*a)%mod);
}
}
int32_t valid(int32_t n, int32_t arr[])
{
set<int> occ;
for(int i = 0; i < n; i++){
if(occ.count(arr[i])){
return 0;
}
occ.insert(arr[i]);
}
pii mpos = {INF,INF};
for(int i = 0; i < n; i++){
mpos = min(mpos,{arr[i],i});
}
int s = mpos.second;
int cnt = mpos.first-1;
for(int i = 0; i < n; i++){
int p = (s+i)%n;
int ex = (cnt%n)+1;
if(arr[p] <= n && ex != arr[p]){
return 0;
}
cnt++;
}
return 1;
}
//----------------------
int32_t replacement(int32_t n, int32_t arr[], int32_t ans[])
{
vector<int> original(n);
pii mpos = {INF,INF};
for(int i = 0; i < n; i++){
mpos = min(mpos,{arr[i],i});
}
if(mpos.first > n) {
iota(original.begin(),original.end(),1);
}else{
int s = mpos.second;
int cnt = mpos.first-1;
for(int i = 0; i < n; i++){
int p = (s+i)%n;
original[p] = (cnt%n)+1;
cnt++;
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
int pt = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n) continue;
pq.push({arr[i],i});
}
int cur = n;
vector<int> order;
while(pq.size()){
int v,p;
tie(v,p) = pq.top(); pq.pop();
while(cur < v){
order.push_back(p);
cur++;
}
}
int nxt = n+1;
for(auto p : order){
ans[pt++] = original[p];
original[p] = nxt++;
}
return pt;
}
//----------------------
int32_t countReplacement(int32_t n, int32_t arr[])
{
if(!valid(n, arr)){
return 0;
}
int cnt = 1;
priority_queue<pii, vector<pii>, greater<pii>> pq;
int pt = 0;
bool f = false;
for(int i = 0; i < n; i++){
if(arr[i] <= n){
f = true;
continue;
}
pq.push({arr[i],i});
}
int cmax = n;
while(pq.size()){
int v,p;
tie(v,p) = pq.top(); pq.pop();
int diff = v-cmax;
int sz = pq.size()+1;
int ch = exp(sz, diff-1);
cnt *= ch;
cnt %= mod;
cmax = v;
}
if(!f) cnt *= n;
cnt %= mod;
return cnt;
}
