Language: C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}
	
deque<int> a;
int L[611111];
int R[611111];
const int INF = int(1e9);
int C[611111];
struct Fenwick
{
	vector<int> t;
    Fenwick(int n)
    {
        t.assign(n+1,0);
    }
    void reset(int n)
    {
		t.assign(n+1, 0);
	}
    void update(int p, int v)
    {
        for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
    }
    int query(int r) //finds [1, r] sum
    {                     
		r++;
        int sum = 0;
        for (; r; r -= (r&(-r))) sum += t[r];
        return sum;
    }
    int query(int l, int r) //finds [l, r] sum
    {
		l++; r++;
		if(l == 0) return query(r);
		return query(r) - query(l-1);
	}
};

int k,n;
int fix(int x)
{
	while(x>=n) x-=n;
	while(x<0) x+=n;
	return x;
}
int cc;
set<ii> S;

void ins(int l, int r)
{
	S.insert(mp(l,r));
	auto it = S.find(mp(l,r));
	while(it!=S.begin())
	{
		int l2=it->fi; int r2=it->se;
		if(r2==l-1)
		{
			cc-=max(0,r-l+1-(k-1));
			cc+=max(0,r-l2+1-(k-1));
			S.erase(mp(l2,r2));
			l=l2;
			it=S.insert(mp(l2,r));
		}
		else break;
	}
	while(next(it)!=S.end())
	{
		int l2=it->fi; int r2=it->se;
		if(l2==r+1)
		{
			cc-=max(0,r-l+1-(k-1));
			cc+=max(0,r2-l+1-(k-1));
			S.erase(mp(l2,r2));
			it=S.insert(mp(l,r2));
			r=r2;
		}
		else break;
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(601111);
	cin>>n;
	int cnt=0;
	for(int i=0;i<n;i++) L[i]=INF,R[i]=-INF;
	a.resize(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; a[i]--;
		if(a[i]==0) cnt++;
		//L[a[i]] = min(L[a[i]],i);
		//R[a[i]] = max(R[a[i]],i);
		C[a[i]]++;
	}
	if(cnt==n)
	{
		cout<<fact[n]<<'\n';
		return 0;
	}
	for(int i=1;i<n;i++)
	{
		if(C[i]==n){cout<<0<<'\n'; return 0;}
	}
	while(a[0]==a[n-1])
	{
		int x = a.back(); a.pop_back();
		a.push_front(x);
	}
	for(int i=0;i<n;i++)
	{
		L[a[i]] = min(L[a[i]],i);
		R[a[i]] = max(R[a[i]],i);
	}
	for(int i=0;i<n;i++)
	{
		if(L[i]<INF)
		{
			if(R[i]-L[i]+1!=C[i])
			{
				cout<<0<<'\n'; return 0;
			}
		}
	}
	k = C[0];
	int ans = 1;
	Fenwick fen(n);
	int ct=0;
	for(int i=1;i<n;i++)
	{
		if(C[i-1]>0)
		{
			for(int j=L[i-1];j<=R[i-1];j++)
			{
				fen.update(j,1); ct++;
			}
			ins(L[i-1],R[i-1]);
		}
		if(C[i]==k) 
		{
			continue;
		}
		if(C[i]>k)
		{
			cout<<0<<'\n'; return 0;
		}
		int l = L[i]; int r = R[i];
		if(C[i]>0)
		{
			int r2=fix(r+1);
			if(!fen.query(r2,r2))
			{
				//must start at r - k + 1
				cout<<0<<'\n'; return 0;
			}
			int l2=fix(l-1);
			if(!fen.query(l2,l2))
			{
				continue;
			}
			int mn = r-k+1;
			ans = mult(ans,k-(r-l));
		} 
		else
		{
			ans=mult(ans,max(0,cc-i));
		}
	}
	cout<<ans<<'\n';
}


Compiler output:
a.cc: In function 'void ins(int, int)':
a.cc:142:45: error: no match for 'operator=' (operand types are 'std::_Rb_tree_const_iterator<std::pair<int, int> >' and 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>')
  142 |                         it=S.insert(mp(l2,r));
      |                                             ^
In file included from /usr/include/c++/14/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:152,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_tree.h:324:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >& std::_Rb_tree_const_iterator<std::pair<int, int> >::operator=(const std::_Rb_tree_const_iterator<std::pair<int, int> >&)'
  324 |     struct _Rb_tree_const_iterator
      |            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:324:12: note:   no known conversion for argument 1 from 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>' to 'const std::_Rb_tree_const_iterator<std::pair<int, int> >&'
/usr/include/c++/14/bits/stl_tree.h:324:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >& std::_Rb_tree_const_iterator<std::pair<int, int> >::operator=(std::_Rb_tree_const_iterator<std::pair<int, int> >&&)'
/usr/include/c++/14/bits/stl_tree.h:324:12: note:   no known conversion for argument 1 from 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>' to 'std::_Rb_tree_const_iterator<std::pair<int, int> >&&'
a.cc:154:45: error: no match for 'operator=' (operand types are 'std::_Rb_tree_const_iterator<std::pair<int, int> >' and 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>')
  154 |                         it=S.insert(mp(l,r2));
      |                                             ^
/usr/include/c++/14/bits/stl_tree.h:324:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >& std::_Rb_tree_const_iterator<std::pair<int, int> >::operator=(const std::_Rb_tree_const_iterator<std::pair<int, int> >&)'
  324 |     struct _Rb_tree_const_iterator
      |            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:324:12: note:   no known conversion for argument 1 from 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>' to 'const std::_Rb_tree_const_iterator<std::pair<int, int> >&'
/usr/include/c++/14/bits/stl_tree.h:324:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >& std::_Rb_tree_const_iterator<std::pair<int, int> >::operator=(std::_Rb_tree_const_iterator<std::pair<int, int> >&&)'
/usr/include/c++/14/bits/stl_tree.h:324:12: note:   no known conversion for argument 1 from 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>' to 'std::_Rb_tree_const_iterator<std::pair<int, int> >&&'