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:
// Only 54 RE
#include <cstdio>
#include <cstring>

#include <set>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long i64;

#define NMAX 300000
#define MOD 998244353

static int n;
static int A[NMAX * 2 + 10], l[NMAX + 10], r[NMAX + 10], c[NMAX + 10];
static vector<int> op[NMAX + 10];

inline int nxt(int i) {
    return i < n ? i + 1 : 1;
}

inline int pre(int i) {
    return i > 1 ? i - 1 : n;
}

inline int pos(int i) {
    return i < 1 ? i + n : (i > n ? i - n : i);
}

inline i64 fac(int x) {
    i64 r = 1;
    for (; x; x--) r = r * x % MOD;
    return r;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", A + i);
    memcpy(A + n + 1, A + 1, sizeof(int) * n);
    if (all_of(A + 1, A + n + 1, [](int x) { return x == A[1]; }))
        printf("%lld\n",
            all_of(A + 1, A + n + 1, [](int x) { return x == 1; }) ? fac(n) : 0);
    else {
        int d = 0, s = 1;
        i64 ans = 1, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (i == 1 && A[1] == A[n]) {
                while (A[i + 1] == A[1]) i++;
                s = i + 1;
                continue;
            }
            if (l[A[i]]) ans = 0;
            l[A[i]] = i;
            for (r[A[i]] = i; A[r[A[i]] + 1] == A[i]; r[A[i]]++) ;
            if (A[i] == 1) d = r[A[i]] - l[A[i]] + 1;
            i = r[A[i]];
        }

        for (int i = 1; i <= n; i++) {
            if (!l[i]) continue;
            int pl = l[i] - d + 1;
            if (pl < 1) {
                op[1].push_back(i);
                op[pos(r[i]) + 1].push_back(-i);
                op[pos(pl)].push_back(i);
            } else if (r[i] > n) {
                op[1].push_back(i);
                op[pos(r[i]) + 1].push_back(-i);
                op[pos(pl)].push_back(i);
            } else {
                op[pos(pl)].push_back(i);
                op[pos(r[i]) + 1].push_back(-i);
            }
        }
        set<int> q;
        for (int i = 1; i <= n; i++) {
            for (int v : op[i]) {
                if (v > 0) q.insert(v);
                else q.erase(q.find(-v));
            }
            if (!q.empty()) c[*q.rbegin()]++;
        }

        for (int i = n; i >= 1; i--) {
            if (!l[i]) {
                cnt++;
                continue;
            }
            int len = r[i] - l[i] + 1;
            if (r[i] > n) r[i] -= n;
            if (len > d) ans = 0;
            if (A[pre(l[i])] < i && A[nxt(r[i])] < i)
                ans = ans * (d - len + 1) % MOD;
            for (int j = 0; j < c[i] - 1; j++, cnt--) ans = ans * cnt % MOD;
        }
        printf("%lld\n", ans);
    }

    return 0;
}