Problem: You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

* For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

* 1 \leq N \leq 3 × 10^5
* 1 \leq A_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1
:
A_N


Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Examples

Input

3
1
2
1


Output

2


Input

5
3
1
4
1
5


Output

0


Input

8
4
4
4
1
1
1
2
2


Output

24


Input

6
1
1
6
2
2
2


Output

0

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 998244353
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
template< typename TTT >
struct SegTree {
	int sz;
	vector<TTT> X;
	SegTree(int N){
		sz = 1;
		while(sz < N) sz <<= 1;
		//初期値代入
		X.assign(2*sz,0);
	}
	TTT f(TTT a,TTT b){
		return a + b;
	}
  	void Set(int k,const TTT x){
    	X[k+sz] = x;
  	}
  	void Build(){
    	for(int k=sz-1;k>0;k--){
      		X[k] = f(X[2*k],X[2*k+1]);
    	}
  	}
  	void Update(int k,const TTT x){
    	k += sz;
    	X[k] = x;
    	while(k >>= 1){
      		X[k] = f(X[2*k+0],X[2*k+1]);
    	}
  	}
  	TTT Query(int a,int b){
    	TTT L = 0, R = 0;
    	for(a += sz,b += sz+1;a < b;a >>= 1,b >>= 1){
      		if(a & 1) L = f(L,X[a++]);
      		if(b & 1) R = f(X[--b],R);
    	}
    	return f(L,R);
  	}
};
int A0[300000];
int A[300000];
int firstplace[300000];
int number[300000];
int minn[300000];
int enableplace[300000];
vector<int> query[300000];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		A0[i] = rei()-1;
	}
	bool ALLzero = true;
	for(int i=0;i<N;i++){
		ALLzero &= A0[i] == 0;
	}
	if(ALLzero){
		long c = 1;
		for(int i=1;i<=N;i++){
			c *= i;
			c %= mod;
		}
		cout << c << endl;
		return;
	}
	int firstzero = -1;
	if(A0[0] == 0 && A0[N-1] != 0){
		firstzero = 0;
	}
	else{
		for(int i=1;i<N;i++){
			if(A0[i] == 0 && A0[i-1] != 0){
				firstzero = i;
				break;
			}
		}
	}
	if(firstzero == -1){
		cout << 0 << endl;
		return;
	}
	for(int i=0;i<N;i++){
		A[i] = A0[(i+firstzero) % N];
		firstplace[i] = -1;
	}
	for(int i=0;i<N;i++){
		number[A[i]]++;
		if(firstplace[A[i]] == -1){
			firstplace[A[i]] = i;
		}
		else if(A[i] != A[i-1]){
			cout << 0 << endl;
			return;
		}
	}
	int n = number[0];
	if(n == 1){
		for(int i=0;i<N;i++){
			if(number[i] != 1){
				cout << 0 << endl;
				return;
			}
		}
		cout << 1 << endl;
		return;
	}
	deque<int> deq;
	for(int i=0;i<n;i++){
		deq.push_back(A[i]);
	}
	minn[0] = 0;
	query[0].push_back(0);
	for(int i=1;i<N;i++){
		if(deq.front() == A[i-1]){
			deq.pop_front();
		}
		if(i+n-1 < N){
			while(!deq.empty() && deq.back() < A[i+n-1]){
				deq.pop_back();
			}
			deq.push_back(A[i+n-1]);
		}
		minn[i] = deq.front();
		query[minn[i]].push_back(i);
	}
	for(int i=0;i<N;i++){
		enableplace[minn[i]]++;
	}
	for(int i=1;i<N;i++){
		enableplace[i] += enableplace[i-1];
	}
	SegTree<int> Seg(N);
	long ans = 1;
	for(int j : query[0]){
		Seg.Update(j,1);
	}
	for(int i=1;i<N;i++){
		if(number[i] == 0){
			ans *= enableplace[i] - i;
		}
		else{
			for(int j : query[i]){
				Seg.Update(j,1);
			}
			int from = firstplace[i]+number[i]-n;
			int to = firstplace[i];
			if(from > to){
				cout << 0 << endl;
				return;
			}
			ans *= Seg.Query(from,to);
		}
		ans %= mod;
	}
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}