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>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define pb push_back
//#define ivorysi
#define MAXN 300005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    	if(c == '-') f = -1;
    	c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 + c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 998244353;
int N,a[MAXN * 2],A[MAXN],st[MAXN][20],val[MAXN],len[MAXN],must[MAXN],sum[MAXN],ql,qr,cnt[MAXN];
bool vis[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
int Query(int l,int r) {
    int t = len[r - l + 1];
    return max(st[l][t],st[r - (1 << t) + 1][t]);
}
void Move(int l,int r) {
    while(qr < r) sum[val[++qr]]++;
    while(ql < l) sum[val[ql++]]--;
}
void Solve() {
    read(N);bool all_1 = 1;
    for(int i = 1 ; i <= N ; ++i) {read(a[i]);a[i + N] = a[i];if(a[i] != 1) all_1 = 0;}
    if(all_1) {
        int res = 1;
        for(int i = 1 ; i <= N ; ++i) res = mul(res,i);
        out(res);enter;return;
    }
    int s = 0;
    for(int i = 2 ; i <= 2 * N ; ++i) {
        if(a[i] == 1 && a[i - 1] != 1) {
            s = i;
            break;
        }
    }
    if(!s) {puts("0");return;}
    for(int i = 1 ; i <= N ; ++i) A[i] = a[s++];
    int p = 1;
    while(A[p] == 1) ++p;
    --p;
    int l = 0;
    for(int i = 1 ; i <= N ; ++i) {
        if(A[i] != A[i - 1]) {
            if(vis[A[i]]) {puts("0");return;}
            vis[A[i]] = 1;l = 0;
        }
        ++l;
        if(l > p) {puts("0");return;}
    }
    for(int i = 1 ; i <= N ; ++i) st[i][0] = A[i];
    for(int j = 1 ; j <= 19 ; ++j) {
        for(int i = 1 ; i <= N ; ++i) {
            if(i + (1 << j) - 1 > N) break;
            st[i][j] = max(st[i][j - 1],st[i + (1 << j - 1)][j - 1]);
        }
    }
    for(int i = 2 ; i <= N ; ++i) len[i] = len[i / 2] + 1;
    for(int i = 1 ; i <= N ; ++i) {
        int r = min(i + p - 1,N);
        val[i] = Query(i,r);
    }
    int t = 0;ql = 1,qr = 0;
    for(int i = 1 ; i <= N ; ++i) {
        if(A[i] != A[i - 1]) {
            if(t) {
                s = max(1,i - p);
                Move(s,t);
                must[A[i - 1]] = sum[A[i - 1]];
                if(!sum[A[i - 1]]) {puts("0");return;}
            }
            t = i;
        }
    }
    s = max(1,N - p + 1);
    Move(s,t);
    must[A[N]] = sum[A[N]];
    if(!sum[A[N]]) {puts("0");return;}
    for(int i = 1 ; i <= N ; ++i) cnt[val[i]]++;
    for(int i = 1 ; i <= N ; ++i) cnt[i] += cnt[i - 1];
    int ans = 1;
    for(int i = 1 ; i <= N ; ++i) {
        if(must[i]) {ans = mul(ans,must[i]);}
        else ans = mul(ans,cnt[i] - (i - 1));
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}