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<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

struct SegT {
private:
	int n; vector<ll> node;
	vector<bool> lazy;
	const ll init_c = 0;
public:
	void init(vector<int> v) {
		n = 1;
		while (n < (int)v.size())n <<= 1;
		node.resize(2 * n - 1,0);
		rep(i, v.size()) {
			node[i + n - 1] = v[i];
		}
		per(i, n - 1) {
			node[i] = node[2 * i + 1] + node[2 * i + 2];
		}
		lazy.resize(2 * n - 1,0);
	}
	ll f(ll a, ll b) {
		return a + b;
	}
	void eval(int k, int l, int r) {
		if (lazy[k]) {
			node[k] = 0;
			if (r - l > 1) {
				lazy[2 * k + 1] = true;
				lazy[2 * k + 2] = true;
			}
			lazy[k] = 0;
		}
	}
	void add(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			lazy[k] =true; eval(k, l, r);
		}
		else {
			add(a, b, k * 2 + 1, l, (l + r) / 2);
			add(a, b, k * 2 + 2, (l + r) / 2, r);
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	ll query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return init_c;
		if (a <= l && r <= b)return node[k];
		else {
			ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
};

struct Seg2T {
private:
	int sz; vector<int> node;
	int init_c = -1;
	bool mi;
public:
	Seg2T(int n,bool m) {
		mi = m;
		if (mi)init_c = mod;
		sz = 1;
		while (sz < n)sz *= 2;
		node.resize(2 * sz - 1, init_c);
	}
	int f(int a, int b) {
		if (mi)return min(a, b);
		else return max(a, b);
	}
	void update(int k, int a) {
		k += sz - 1;
		node[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	int query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = sz;
		if (r <= a || b <= l)return init_c;
		else if (a <= l && r <= b)return node[k];
		else {
			int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
};
int n; vector<int> a;
vector<P> mindist;

bool calc() {
	mindist.resize(n+1);
	Seg2T le(n + 1, true), ri(n + 1, false);
	vector<bool> exi(n + 1, false);
	rep(i, n) {
		if (exi[a[i]])return false;
		exi[a[i]] = true;
		while (i + 1 < n&&a[i] == a[i + 1])i++;
	}
	rep(i, n) {
		int l = i; while (i + 1 < n&&a[i] == a[i + 1])i++;
		ri.update(a[i], i);
		mindist[a[i]].first = ri.query(a[i]+1,n+1);
	}
	per(i, n) {
		int r = i; while (i - 1 >= 0 && a[i - 1] == a[i])i--;
		le.update(a[i], i);
		mindist[a[i]].second = le.query(a[i]+1, n + 1);
	}
	return true;
}
void solve() {
	cin >> n;
	a.resize(n); rep(i, n)cin >> a[i];
	if (a[0] == 1) {
		per(i, n) {
			if (a[i] > 1) {
				vector<int> b;
				rep(j, n) {
					b.push_back(a[(i +1+ j) % n]);
				}
				a = b;
				break;
			}
		}
	}
	else {
		rep(i, n) {
			if (a[i] == 1) {
				vector<int> b;
				rep(j, n) {
					b.push_back(a[(i + j) % n]);
				}
				a = b;
				break;
			}
			else if (i == n - 1) {
				cout << 0 << endl; return;
			}
		}
	}
	int k = n;
	rep(i, n) {
		if (a[i]>1) {
			k = i; break;
		}
	}
	//cout << k << endl;
	if (k == n) {
		ll ans = 1; rep1(i, n)ans = ans * i%mod; cout << ans << endl; return;
	}
	if (k == 1) {
		sort(a.begin(), a.end());
		rep(i, n) {
			if (a[i] != i + 1) {
				cout << 0 << endl; return;
			}
		}
		cout << 1 << endl; return;
	}
	vector<int> v(n,1);
	vector<bool> used(n+1,false);
	vector<P> loc(n + 1);
	//v[0] = 0;
	used[1] = true;
	//cout << k << endl;
	vector<ll> rr(n + 1, 1);

	if (!calc()) {
		cout << 0 << endl; return;
	}
	Rep(i, k, n) {
		used[a[i]] = true;
		int le = i;
		while (i + 1 < n&&a[i] == a[i + 1])i++;
		loc[a[i]] = { le,i };
		if (i - le + 1 > k) {
			cout << 0 << endl; return;
		}
		int lle = max(i - k + 1, mindist[a[i]].first + 1);
		int rri = min(le, mindist[a[i]].second - k);
		if (rri - lle < 0) {
			cout << 0 << endl; return;
		}

		rr[a[i]] = rri - lle + 1;
		//v[i - k + 1] = 0;
	}
	//rep1(i, n)cout << used[i]; cout << endl;
	SegT st;
	st.init(v);
	vector<ll> rest(n + 1, 0);
	per1(i, n) {
		if (used[i]) {
			int le = loc[i].first, ri = loc[i].second;
			int sle = le - k + 1;
			if (sle >= 0) {
				st.add(sle, ri + 1);
			}
			else {
				st.add(0, ri + 1);
				st.add(sle + n, n);
			}
		}
		else {
			rest[i] = st.query(0, n);
		}
	}
	ll ans = 1;
	//cout << ans << endl;
	int tmp = 0;
	rep1(i, n) {
		//cout << i<<" "<<ans << endl;
		if (used[i]) {
			ans = ans * rr[i] % mod;
			tmp++;
			continue;
		}
		ll num = rest[i] - tmp;
		if (num <= 0) {
			cout << 0 << endl; return;
		}
		ans = ans * num%mod;
		tmp++;
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
		return 0;
}