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;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream& operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream& operator<<(ostream &os, vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream& operator<<(ostream &os, set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream& operator<<(ostream &os, pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream& operator<<(ostream &os, map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;


template <typename T>
struct SegTree
{
    int N;
    int head;
    vector<T> x;
    T defaultT;
    using func = function<T(const T&, const T&)>;
    func tree_update;

    T _query_search(int begin, int end, int pos, int l, int r)
    {
        if (r <= begin || l >= end) return defaultT;
        if (l >= begin && r <= end) return x[pos];
        T v_l = _query_search(begin, end, 2*pos+1, l, (l+r)/2);
        T v_r = _query_search(begin, end, 2*pos+2, (l+r)/2, r);
        return tree_update(v_l, v_r);
    }

    SegTree(int N, T val_default, func f) : N(N), defaultT(val_default), tree_update(f)
    {
        int N_tmp = 1;
        while (N_tmp < N) N_tmp <<= 1;
        x = vector<T>(N_tmp*2, defaultT);
        head = N_tmp - 1;
    }

    void update(int pos, T val)
    {
        pos += head;
        x[pos] = val;
        while (pos)
        {
            pos = (pos - 1) / 2;
            x[pos] = tree_update(x[pos*2+1], x[pos*2+2]);
        }
    }
    T query(int begin, int end)
    {
        return _query_search(begin, end, 0, 0, (int)x.size() / 2);
    }
};

constexpr int Nmax = 300001;
int N;

void dame()
{
    cout << 0 << endl;
    exit(0);
}

void easy_check(const vector<int> &A)
{
    vector<int> count_(N + 1);
    int now = 0;
    while (A[now] == A[0]) now++;

    int a = A[0];
    FOR(i, now, N + 1)
    {
        if (a != A[i]) count_[A[i]]++;
        a = A[i];
        if (count_[a] > 1) dame();
    }
}


constexpr lint MOD = 998244353;
vector<lint> fac;
void facInit(int nmax)
{
    fac = vector<lint>(nmax + 1, 1);
    for (int i = 2; i <= nmax; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
    }
}


signed main()
{
    SegTree<int> rmq(Nmax * 2, 0, [](int a, int b) { return max(a, b); });

    cin >> N;
    vector<int> A(N);
    cin >> A;

    map<int, int> ma;
    REP(i, N) ma[A[i]]++;
    if (ma[1] == N) { facInit(N); cout << fac[N] << endl; return 0; }

    int d = 0;
    REP(i, N) d += (A[i] == 1);


    A.push_back(A[0]);
    easy_check(A);
    for (auto pa : ma) if (pa.second > d) dame();
    A.pop_back();

    REP(i, N) rmq.update(i, A[i]);
    REP(i, N) rmq.update(i + N, A[i]);

    vector<int> kakutei(N, 0);
    vector<int> hindo(N + 1);
    REP(i, N)
    {
        int iprev = (i + N - 1) % N;
        if (A[i] > A[iprev])
        {
            if (kakutei[(i - d + N) % N] && kakutei[(i - d + N) % N] != A[iprev]) dame();
            kakutei[(i - d + N) % N] = A[iprev];
        }
        else if (A[i] < A[iprev])
        {
            if (kakutei[i] && kakutei[i] != A[i]) dame();
            kakutei[i] = A[i];
        }
    }
    REP(i, N) if (!kakutei[i]) hindo[rmq.query(i, i + d)]++;

    vector<int> used(N + 1);
    for (auto v : kakutei) if (v)
    {
        if (used[v] == 1) dame();
        used[v] = 1;
    }

    lint now = 1;
    lint ans = 1;
    lint eraberu = 0;
    while (now <= N)
    {
        eraberu += hindo[now];
        if (used[now])
        {
            now++;
            continue;
        }
        if (ma[now]) ans = ans * (d + 1 - ma[now]) % MOD;
        else ans = ans * eraberu % MOD;
        eraberu--;
        now++;
    }
    cout << ans << endl;
}