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 <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <cmath>
#include <cassert>

#define P 998244353
#define M 600010

using namespace std;

int n, A[M], L[M], R[M], Fac[M], QL[M], QR[M], Nw[M];

int isq2[M];

vector <int> arrg;

void GG() {
    puts("0");
    exit(0);
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) Fac[i] = !i ? 1 : (long long) Fac[i - 1] * i % P;
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    int fir1 = 1;
    while(fir1 <= n && A[fir1] == 1) fir1++;
    if(fir1 > n) return printf("%d\n", Fac[n]), 0; else {
        int ff = fir1;
        while(fir1 <= n && A[fir1] != 1) fir1++;
        if(fir1 > n) {
            if(ff == 1) GG();
            else fir1 = 1;
        }
    }
    for(int i = 1; i < fir1; i++) A[i + n] = A[i];
    for(int i = 1; i <= n; i++) A[i] = A[i + fir1 - 1];
    for(int i = 1; i <= n; i++) {
        if(A[i] != A[i - 1]) {
            if(L[A[i]]) GG();
            L[A[i]] = i;
            R[A[i - 1]] = i - 1;
        }
    }
    R[A[n]] = n;
    arrg.clear();
    arrg.push_back(R[1]);
    A[n + 1] = 1;
    QL[1] = (QR[1] = R[1]);
    for(int i = 2; i <= n; i++) {
        if(!L[i]) {
            isq2[(int) arrg.size() - 1]++;
            continue;
        }
        if(R[i] - L[i] > R[1] - L[1]) GG();
        bool b1 = A[L[i] - 1] < i, b2 = A[R[i] + 1] < i;
        if(!b1 && !b2) {
            if(R[i] - L[i] != R[1] - L[1]) GG();
            QL[i] = (QR[i] = R[i]);
        } else if(!b1 && b2) {
            QL[i] = (QR[i] = L[i] + R[1] - L[1]);
        } else if(b1 && !b2) {
            QL[i] = (QR[i] = R[i]);
        } else {
            QL[i] = R[i];
            QR[i] = L[i] + R[1] - L[1];
        }
        for(int j = (b1 ? L[i] : L[i] + R[1] - L[1]); j <= (b2 ? R[i] + R[1] - L[1] : R[i]); j++)
            arrg.push_back((j - 1) % n + 1);
    }
    long long ans = 1;
    for(int i = 1; i <= n; i++) if(QL[i]) {
        int nw = 0;
        for(int j = QL[i]; j <= QR[i]; j++)
            if(!Nw[(j - 1) % n + 1]) nw++;
        if(!nw) GG();
        ans = (long long) ans * nw % P;
        for(int j = QL[i]; j <= QR[i]; j++)
            if(!Nw[(j - 1) % n + 1]) {
                Nw[(j - 1) % n + 1] = 1;
                break;
            }
    }
    assert(arrg.size() == n);
    int nw = 0;
    for(int i = 0; i < n; i++) {
        if(!Nw[arrg[i]]) nw++;
        while(isq2[i]--) ans = ((long long) ans * nw--) % P;
    }
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}