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:

//pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "circular"

const int MAX_N = 300002;
const int MOD = 998244353;

namespace dsu {
    int lab[MAX_N];

    void init() {
        memset(lab, -1, sizeof(lab));
    }

    int findset(int u) {
        return lab[u]<0 ? u : lab[u]=findset(lab[u]);
    }

    int len(int s) {
        return -lab[findset(s)];
    }

    bool uni(int s, int t) {
        s = findset(s);
        t = findset(t);
        if (s==t)
            return false;
        lab[t] += lab[s];
        lab[s] = t;
        return true;
    }
};

int n, a[MAX_N], nxt[MAX_N], l[MAX_N], r[MAX_N];

void readInput() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
        --a[i];
    }
}

int calc(int v, int k) {
    if (v<k)
        return 0;
    return v-k+1;
}

int dist(int l, int r) {
    if (l<=r)
        return r - l + 1;
    return n - l + r + 1;
}

int64_t solve() {
    a[n+1] = n;
    for (int i=n-1; i>=0; --i) {
        if (a[i]!=a[(i+1)%n])
            nxt[i] = i;
        else
            nxt[i] = nxt[i+1];
    }
    for (int i=n-1; i>=0; --i) {
        if (a[i]!=a[(i+1)%n])
            nxt[i] = i;
        else
            nxt[i] = nxt[(i+1)%n];
    }
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    for (int i=0; i<n; ++i) {
        if (a[i]!=a[(i-1+n)%n]) {
            if (l[a[i]]!=-1)
                return 0;
            l[a[i]] = i;
            r[a[i]] = nxt[i];
        }
    }
    if (a[0]==0 && l[0]==-1) {
        int64_t res = 1;
        for (int i=1; i<=n; ++i)
            res = res * i % MOD;
        return res;
    }
    if (l[0]==-1)
        return 0;
    int k = dist(l[0], r[0]), s = 0;
    for (int i=0; i<n; ++i) {
        if (l[i]!=-1 && dist(l[i], r[i])>k)
            return 0;
    }
    int64_t res = 1;
    dsu::init();
    for (int i=0; i<n; ++i) {
        if (l[i]==-1) {
            if (dsu::len(0)==n)
                res = res * (n - i) % MOD;
            else
                res = res * (s - i) % MOD;
        }
        else if (a[(l[i]-1+n)%n]>i || a[(r[i]+1)%n]>i) {
            if (a[(l[i]-1+n)%n]>i && a[(r[i]+1)%n]>i && dist(l[i], r[i])!=k)
                return 0;
        }
        else {
            res = res * (k - dist(l[i], r[i]) + 1) % MOD;
        }
        if (l[i]==-1)
            continue;
        for (int j=l[i]; j!=r[i]; j = (j + 1) % n)
            dsu::uni(j, (j+1)%n);
        if (a[(l[i]-1+n)%n]<i) {
            s -= calc(dsu::len((l[i]-1+n)%n), k);
            dsu::uni(l[i], (l[i]-1+n)%n);
        }
        if (a[(r[i]+1)%n]<i) {
            if (dsu::findset(r[i])!=dsu::findset((r[i]+1)%n))
                s -= calc(dsu::len((r[i]+1)%n), k);
            dsu::uni(r[i], (r[i]+1)%n);
        }
        s += calc(dsu::len(l[i]), k);
    }
    assert(res>=0);
    return res;
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
	cout << solve();
}