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;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 998244353;

const int MAXN = 3e5 + 5;

int v[MAXN];

ll f[MAXN];

int l[MAXN], r[MAXN];
int coord[MAXN];

void solve(){
	f[0] = 1;
	REP(i, 1, MAXN) {
		f[i] = (f[i - 1] * i) % MOD;
	}
	
	
	int n;
	scanf("%d", &n);
	REP(i, 0, n) {
		scanf("%d", &v[i]);
	}
	if (v[0] == 1 && v[n - 1] == 1) {
		int s = n - 1;
		for(; s >= 0 && v[s] == 1; s--);
		if (s < 0) {
			printf("%lld\n", f[n]);
			return;
		}
		rotate(v, v + s + 1, v + n);
	}
	
	/*REP(i, 0, n) {
		printf("%d ", v[i]);
	}*/
	
	int s = 0;
	for(; s < n && v[s] != 1; s++);
	if (s == n) {
		printf("0\n");
		return;
	}
	
	rotate(v, v + s, v + n);
	int k = 0;
	for(k = 0; k < n && v[k] == 1; k++);
	
	l[1] = 0; r[1] = k - 1;
	REPN(i, k, n) {
		if (v[i] != v[i - 1]) {
			r[v[i - 1]] = i - 1;
			if (i != n) {
				if (v[i] == 1 || l[v[i]]) {
					
					printf("0\n");
					return;
				}
				l[v[i]] = i;
			}
		}
	}

	ll ans = 1ll;
	int vv = 0;
	REPN(i, 2, n) {
		if (!l[i]) {
			if (vv == 0) {
				
				printf("0\n");
				return;
			}
			ans = (ans * vv) % MOD;
			vv--;
			continue;
		}
		if (r[i] - l[i] >= k) {
			//printf("0\n");
			printf("0\n");
			return;
		}
		
		int lpos = -1, rpos = -1;
		int prv_i = v[l[i] - 1], nxt_i = v[(r[i] + 1) % n];
		if (prv_i > i) {
			if (nxt_i > i && r[i] - l[i] < k - 1) {
				//printf("0\n");
				printf("0\n");
				return;
			}
			//printf("1\n");
			lpos = l[i];
			rpos = l[i];
			coord[i] = lpos;
			
			if (nxt_i < i) {
				vv += r[i] - l[i];
			}
		} else if (nxt_i > i) {
			//printf("2\n");
			lpos = r[i] - k + 1;
			rpos = r[i] - k + 1;
			coord[i] = lpos;
			
			vv += r[i] - l[i];
		} else {
			//printf("3\n");
			lpos = max(r[i] - k + 1, coord[prv_i] + 1);
			rpos = min(l[i], (coord[nxt_i] - 1 + n) % n);
			
			vv += (coord[nxt_i] + n - coord[prv_i] - 2) % n;
		}
		
		/*if (v[(l[i] - 1 + n) % n] < i) {
			vv += l[i] - l[v[l[i] - 1]] - 1;
		}
		if (v[(r[i] + 1) % n] < i) {
			vv += -r[i] + r[v[r[i] + 1]] - 1;
		}*/
		//printf("%d\n", k);
		//printf("%d %d %d %d %d %d\n", i, l[i], r[i], lpos, rpos, vv);
		
		ans = (ans * (rpos - lpos + 1)) % MOD;
	}
	//printf("0\n");
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}