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 <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

bool used[333333];
int mp[333333];

int main(){

	ll n;cin >> n;
	vector<ll> v(n);
	set<ll> s;
	REP(i,n){
		cin >> v[i];
		s.insert(v[i]);
	}

	if(s.size() == 1){
		if(s.count(1)){
			ll ans = 1;
			REP(i,n){
				ans *= i+1;
				ans %= MOD;
			}
			cout << ans << endl;
		}
		else{
			cout << 0 << endl;
		}
		return 0;
	}

	deque<int> deq;
	deque<int> ldeq;
	ll now = -1,pla = 0,st = -1,ans = 1,malen = 0,nlen = 0;
	bool flag = true;
	vector<pair<pair<ll,ll>,pair<ll,ll>>> seica;
	while(1){
		if(pla == st)break;
		if(v[pla] != now){
			now = v[pla];
			deq.push_back(now);
			ldeq.push_back(nlen);
			if(deq.size() > 3)deq.pop_front();
			if(ldeq.size() > 3)ldeq.pop_front();
			if(deq.size() == 3) {
				if(flag){
					st = pla;
					flag = false;
				}
				if(used[deq[1]]){
					cout << 0 << endl;
					return 0;
				}
				seica.PB(MP(MP(deq[1],ldeq[2]),MP(deq[0],deq[2])));
				used[deq[1]] = true;
				malen = max(malen,nlen);
			}
			nlen = 1;
		}
		else{
			nlen++;
		}
		pla = (pla + 1) % n;
	}
	sort(ALL(seica));
	if(seica[0].FI.FI != 1 || malen > seica[0].FI.SE){
		cout << 0 << endl;
		return 0;
	}

	deque<pair<int,int>> p_deq;
	pla = 0;
	REP(i,n){
		while(pla - i < malen){
			while(p_deq.size() && p_deq[p_deq.size()-1].FI < v[pla%n])p_deq.pop_back();
			p_deq.push_back(MP(v[pla%n],pla));
			pla++;
		}
		while(p_deq[0].SE < i)p_deq.pop_front();
		mp[p_deq[0].FI]++;
	}

	now = 0;
	pla = 0;
	for(ll i = 1;i <= n;i++){
		pla += mp[i];
		if(now < seica.size() && seica[now].FI.FI == i){
			if(i < seica[now].SE.FI && i < seica[now].SE.SE && seica[now].FI.SE != malen){
				cout << 0 << endl;
				return 0;
			}
			if(i > seica[now].SE.FI && i > seica[now].SE.SE){
				ans *= malen - seica[now].FI.SE + 1;
				ans %= MOD;
			}
			now++;
		}
		else{
			ans *= pla;
			ans %= MOD;
		}
		pla--;
	}

	cout << ans << endl;

	return 0;
}