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(int i=a;i<b;i++)
#define rrep(i,a,b) for(int 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; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<998244353> mint;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



int N, A[601010], B[601010];
vector<int> P[301010];
int L[301010];
//---------------------------------------------------------------------------------------------------
mint solve() {
    if (count(A, A + N, 0) == 0) return 0;
    if (count(A, A + N, 0) == N) {
        mint res = 1;
        rep(i, 0, N) res *= i + 1;
        return res;
    }

    // 0の連続領域が始まりになるよう変換
    rep(i, 0, N) if (A[i] == 0 and 0 < A[(i - 1 + N) % N]) {
        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;
    }

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

    empty.insert(4 * N); // 番兵
    rep(i, 0, 2 * N) empty.insert(i);

    rep(i, 0, N) {
        L[i] = P[i].size();

        // 0領域の長さ以上のものは作れない
        if (L[0] < L[i]) return 0;

        // 現れない場合は、完全に隠れる領域の個数分の組み合わせがある
        if (L[i] == 0) {
            res *= numfree;
            numfree--;
            continue;
        }

        // 連続領域じゃない場合はダメ
        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);
        }

        int x = P[i][0];

        // 左が埋まってない and 右が埋まってない and 長さが短い → NG
        if (i < A[x + N - 1] and i < A[x + L[i]] and L[i] != L[0]) return 0;

        // 左が埋まってる and 右が埋まってる → 埋められる幅分の組み合わせ数
        if (A[x + N - 1] < i and A[x + L[i]] < i) res *= L[0] - L[i] + 1;

        auto it = unused.lower_bound(P[i][0] - (L[0] - 1));
        while (it != unused.end() and *it <= P[i].back()) {
            auto it2 = empty.lower_bound(*it);
            if (*it2 - *it < L[0]) {
                // 候補と次の埋まっていない部分との差がL[0]未満ならおおえない
                // ので、*it2以降で探す
                it = unused.lower_bound(*it2);
            } else {
                numfree++;
                it = unused.erase(it);
            }
        }

        // 埋めた領域の最初は埋まってしまうので、numfreeは1つ分減らしておく
        numfree--;
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        cin >> A[i];
        A[i]--;
    }
    cout << solve() << endl;
}