#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int max_sub_1 = 2.5e5 + 5;
int valid(int n, int inputSeq[])
{
bool seen_sub_1[max_sub_1] = { 0 };
auto it = min_element(inputSeq, inputSeq + n);
int val = *it, pos = it - inputSeq;
int start_pos = pos;
while (pos != start_pos || val == *it)
{
if (inputSeq[pos] == val)
{
val++, pos++;
if (pos >= n) pos -= n;
val = min(val, n);
continue;
}
if (inputSeq[pos] > n)
{
if (seen_sub_1[inputSeq[pos]]) return 0;
seen_sub_1[inputSeq[pos]] = true;
val++, pos++;
if (pos >= n) pos -= n;
val = min(val, n);
continue;
}
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int min_val, min_pos;
auto min_it = min_element(gondolaSeq, gondolaSeq + n);
min_val = *min_it, min_pos = min_it - gondolaSeq;
vector <pii> numbers;
int val = min_val, pos = min_pos;
if (val > n) val = 1;
int replacement_pos = 0;
bool start = true;
while (pos != min_pos || start)
{
start = false;
if (gondolaSeq[pos] == val)
{
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
if (gondolaSeq[pos] > n)
{
numbers.emplace_back(pii(gondolaSeq[pos], val));
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
abort();
}
if (numbers.empty()) return 0;
sort(numbers.begin(), numbers.end());
int last_val = n;
for (const pii &p : numbers)
{
replacementSeq[replacement_pos++] = p.second;
last_val++;
while (last_val < p.first) replacementSeq[replacement_pos++] = last_val++;
}
return replacement_pos;
}
constexpr ll mod = 1e9 + 7, max_exp = 1e5 + 5, bits_max_exp = 31 - __builtin_clz(max_exp);
void modf(ll &num)
{
if (num >= mod) num %= mod;
}
ll binary_exp(ll base, ll exp)
{
if (exp == 0) return 1;
ll output = 1;
for (int i = 0; i < bits_max_exp; i++)
{
if (exp & (1 << i))
{
output *= base;
modf(output);
}
base *= base;
modf(base);
}
return output;
}
int countReplacement(int n, int inputSeq[])
{
int validity = valid(n, inputSeq);
if (validity == 0) return 0;
int max_el = *max_element(inputSeq, inputSeq + n);
if (max_el == n) return 1;
int min_val, min_pos;
auto min_it = min_element(inputSeq, inputSeq + n);
min_val = *min_it, min_pos = min_it - inputSeq;
vector <ll> numbers;
int val = min_val, pos = min_pos;
if (val > n) val = 1;
bool start = true;
while (pos != min_pos || start)
{
start = false;
if (inputSeq[pos] == val)
{
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
if (inputSeq[pos] > n)
{
numbers.emplace_back(inputSeq[pos]);
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
abort();
}
if (numbers.empty()) return 0;
sort(numbers.begin(), numbers.end(), greater<ll>());
ll last_val = n, next_val;
ll output = 1;
for (size_t i = numbers.size(); i > 0; i--)
{
next_val = numbers.back();
numbers.pop_back();
output *= binary_exp(i, next_val - last_val - 1);
modf(output);
last_val = next_val;
}
assert(output != 0);
return (int)output;
}
