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;

const int mod = 998244353;
const int MN = 300010;

int N;
int A[MN], B[MN], chk[MN];
struct Seg {
    int l, r, v;
};
vector<Seg> seg;

struct BIT {
    vector<int> tree, lazy;
    void init() {
        tree = vector<int>(4 * N, 0);
        lazy = vector<int>(4 * N, 0);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] = max(tree[2*n], lazy[n]);
            lazy[2*n] = max(lazy[2*n], lazy[n]);
            tree[2*n + 1] = max(tree[2*n + 1], lazy[n]);
            lazy[2*n + 1] = max(lazy[2*n + 1], lazy[n]);
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, int val, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] = max(tree[n], val);
            lazy[n] = max(lazy[n], val);
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, val, l, m, 2*n);
        upd(a, b, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit;

int cnt[MN], del[MN];

int main() {
    scanf("%d", &N);

    bool ok = true;
    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        A[i]--;

        if(A[i]) ok = false;
    }

    if(ok) {
        int ans = 1;
        for(int i = 1; i <= N; i++) ans = 1LL * ans * i % mod;
        printf("%d", ans);
        return 0;
    }

    int p = -1;
    for(int i = 0; i < N; i++) {
        int j = (i + 1) % N;

        if(A[i] && !A[j]) {
            p = j;
            break;
        }
    }

    if(p == -1) {
        printf("0");
        return 0;
    }

    for(int i = 0; i < N; i++) {
        B[i] = A[ (p + i) % N ];
    }

    int st = 0;
    for(int i = 0; i < N; i++) {
        if(chk[ B[i] ]) {
            printf("0");
            return 0;
        }

        if(i == N - 1 || B[i + 1] != B[i]) {
            chk[ B[i] ] = 1;
            seg.push_back({ st, i, B[i] });
            st = i + 1;
        }
    }

    int len = seg[0].r - seg[0].l + 1;
    for(int i = 0; i < seg.size(); i++) {
        if(seg[i].r - seg[i].l + 1 > len) {
            printf("0");
            return 0;
        }
        if(i && i < (int)seg.size() - 1 && seg[i - 1].v > seg[i].v && seg[i + 1].v > seg[i].v) {
            if(seg[i].r - seg[i].l + 1 != len) {
                printf("0");
                return 0;
            }
        }
    }

    bit.init();
    for(int i = 0; i < seg.size(); i++) {
        int l = max(0, seg[i].l - len + 1);
        bit.upd(l, seg[i].r, seg[i].v, 0, N - 1, 1);
    }
    for(int i = 0; i < N; i++) {
        cnt[ bit.quer(i, i, 0, N - 1, 1) ]++;
    }

    del[0] = 1;
    cnt[0]--;
    for(int i = 1; i < seg.size(); i++) {
        if(seg[i - 1].v > seg[i].v) {
            if(bit.quer(seg[i].l, seg[i].l, 0, N - 1, 1) > seg[i].v) {
                printf("0");
                return 0;
            }
            del[ seg[i].v ] = 1;
            cnt[ seg[i].v ]--;
        }
        if(!del[ seg[i - 1].v ] && seg[i - 1].v < seg[i].v) {
            if(seg[i - 1].r - len + 1 < 0 || bit.quer(seg[i - 1].r - len + 1, seg[i - 1].r - len + 1, 0, N - 1, 1) > seg[i - 1].v) {
                printf("0");
                return 0;
            }
            del[ seg[i - 1].v ] = 1;
            cnt[ seg[i - 1].v ]--;
        }
    }

    int ans = 1;
    for(int i = 1; i < seg.size(); i++) {
        int j = (i + 1) % (int)seg.size();
        if(seg[i - 1].v < seg[i].v && seg[j].v < seg[i].v) {
            del[ seg[i].v ] = 1;
            cnt[ seg[i].v ]--;

            int l = seg[i].r - len + 1;
            int r = seg[i].l;
            int s = l, e = r, p = l - 1, q = r + 1;
            while(s <= e) {
                int m = (s + e)>>1;

                if(bit.quer(l, m, 0, N - 1, 1) > seg[i].v) {
                    p = m;
                    s = m + 1;
                }
                else e = m - 1;
            }
            s = l, e = r;
            while(s <= e) {
                int m = (s + e)>>1;

                if(bit.quer(m, r, 0, N - 1, 1) > seg[i].v) {
                    q = m;
                    e = m - 1;
                }
                else s = m + 1;
            }

            if(q <= p + 1) {
                printf("0");
                return 0;
            }

            ans = 1LL * ans * (q - p - 1) % mod;
        }
    }

    for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1];
    int x = 0;
    for(int i = 0; i < N; i++) if(!del[i]) {

        //cout << i << ' ' << cnt[i] << ' ' << x << endl;

        if(cnt[i] - x <= 0) {
            printf("0");
            return 0;
        }

        ans = 1LL * ans * (cnt[i] - x) % mod;
        x++;
    }

    printf("%d", ans);
}