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 <cstdio>
#include <algorithm>
using namespace std;

constexpr int mod = 998244353;
int fac[300001], inv[300001];
int a[300000];
int minx[300000], maxx[300000];

int solve(int n) {
    int n0 = count(a, a + n, 0);
    if (n0 == 0)
        return 0;
    if (n0 == n)
        return fac[n];

    if (a[0] != 0) {
        rotate(a, find(a, a + n, 0), a + n);
    } else {
        int j = 0;
        while (a[j] == 0)
            j++;
        // a[j] != 0
        rotate(a, a + (n - (n0 - j)), a + n);
    }

    if (find(a + n0, a + n, 0) != a + n)
        return 0;

    fill_n(minx, n, n);
    fill_n(maxx, n, -1);

    for (int i = 0; i < n; i++) {
        minx[a[i]] = min(minx[a[i]], i);
        maxx[a[i]] = max(maxx[a[i]], i);
    }

    int ans = 1, num = 0;
    for (int i = n - 1; i >= 1; i--) {
        num++;
        if (maxx[i] < minx[i])
            continue;
        if (count(a + minx[i], a + maxx[i] + 1, i)
                != maxx[i] - minx[i] + 1)
            return 0;

        int l = maxx[i] - (n0 - 1), r = minx[i];
        int ll = minx[i] - (n0 - 1), rr = maxx[i];

        if (a[minx[i] - 1] > i) {
            l = max(l, minx[i]);
            ll = max(ll, minx[i]);
        }
        if (maxx[i] + 1 < n && a[maxx[i] + 1] > i) {
            r = min(r, maxx[i] - (n0 - 1));
            rr = min(rr, maxx[i] - (n0 - 1));
        }

        if (l > r)
            return 0;

        ans = (long) ans * (r - l + 1) % mod;
        num--;

        if (rr - ll > num)
            return 0;

        ans = (long) ans * fac[num] % mod *
                    inv[num - (rr - ll)] % mod;
        num -= rr - ll;
    }

    // fprintf(stderr, "num=%d\n", num);

    return ans;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= 300000; i++)
        fac[i] = (long) fac[i - 1] * i % mod;
    inv[300000] = 988693096;
    for (int i = 300000; i >= 1; i--)
        inv[i - 1] = (long) inv[i] * i % mod;

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i), a[i]--;
    printf("%d\n", solve(n));
}