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>
#define rep(i,a,b) for(i=a;i<b;i++)
#define rrep(i,a,b) for(i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 
ll mo = 998244353;
int N, A[1201010], B[1201010];
vector<int> P[301010];
int L[301010];
//---------------------------------------------------------------------------------------------------
ll solve() {
    int i, j, k, l, r, x, y; string s;

    if (count(A, A + N, 0) == 0) return 0;
    if (count(A, A + N, 0) == N) {
        ll ret = 1;
        rep(i, 0, N) ret = ret * (i + 1) % mo;
        return ret;
    }

    rep(i, 0, N) if (A[i] == 0 && A[(i + N - 1) % N]>0) {
        rep(j, 0, 2 * N) B[j] = A[(i + j) % N];
        rep(j, 0, 2 * N) A[j] = B[j];
        rep(j, 0, N) P[A[j]].push_back(j);
        break;
    }

    ll res = 1;
    set<int> empty, unused;
    int numfree = 0;

    empty.insert(4 * N);
    rep(i, 0, N) empty.insert(i), empty.insert(i + N);
 
    rep(i, 0, N) {
        L[i] = P[i].size();
 
        // 0領域の長さ以上のものは作れない
        if (L[0] < L[i]) return 0;
 
        // 現れない場合は、完全に隠れる領域の個数分の組み合わせがある
        if (L[i] == 0) {
            res = res * numfree%mo;
            numfree--;
        }
        else {
            // 連続領域じゃない場合はダメ
            if (P[i][0] + L[i] - 1 != P[i].back()) return 0;

            fore(p, P[i]) {
                empty.erase(p);
                empty.erase(p + N);
                unused.insert(p);
            }

            x = P[i][0];

            if (A[x + N - 1] > i && A[x + L[i]] > i && L[i] != L[0]) return 0;
            if (A[x + N - 1]<i && A[x + L[i]]<i) res = res * (L[0] - L[i] + 1) % mo;

            auto it = unused.lower_bound(P[i][0] - (L[0] - 1));
            while (it != unused.end() && *it <= P[i].back()) {
                auto it2 = empty.lower_bound(*it);
                if (*it2 - *it<L[0]) {
                    it = unused.lower_bound(*it2);
                }
                else {
                    numfree++;
                    it = unused.erase(it);
                }
            }

            // 埋めた領域の最初は埋まってしまうので、numfreeは1つ分減らしておく
            numfree--;
        }
    }
 
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int i;
    cin >> N;
    rep(i, 0, N) {
        cin >> A[i];
        A[i]--;
    }
    cout << solve() << endl;
}