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 <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 998244353


//ここから編集する
class Solve {
public:
    int N;

    vector<int> A;

    vector<vector<int> > gr;
    int K;

    void input() {
        deque<int> A;
        cin >> N;
        bool app = false;
        rep(i, 0, N) {
            int tmp;
            cin >> tmp;
            A.push_back(tmp);
            this->A.push_back(tmp);
            if (tmp == 1) app = true;
        }
        if (!app) {
            cout << 0 << endl;
            exit(0);
        }
        if (all1()) {
            ll ans = 1ll;
            for (int i = 1; i <= N; ++i) {
                (ans *= i) %= MOD;
            }
            cout << ans << endl;
            exit(0);
        }

        while (A[0] != 1) {
            int tmp = A.back();
            A.push_front(tmp);
            A.pop_back();
        }

        while (A.back() == 1) {
            int tmp = A.back();
            A.push_front(tmp);
            A.pop_back();
        }

        this->A = vector<int>(A.begin(), A.end());

    }

    bool all1() {
        for (auto a : A) {
            if (a != 1) return false;
        }
        return true;
    }

    void solve() {
        input();
        gr.resize(N + 1);
        for (int i = 0; i < N; ++i) {
            gr[A[i]].push_back(i);
        }
        K = gr[1].size(); //連続する区間が何個
        for(int i = 1; i <= N; ++i){
            if(gr[i].size() > 0 && gr[i].back() - gr[i].front() + 1 != gr[i].size()){
                cout << 0 << endl;
                exit(0);
            }
        }


        A.push_back(1);
        ll rest = 0;
        ll ans = 1ll;
        for (int i = 2; i <= N; ++i) {
            if (gr[i].size() == 0) {
                (ans *= rest) %= MOD;
                rest--;
            } else if (gr[i].size() > K) {
                cout << 0 << endl;
                exit(0);
            } else if (gr[i].size() < K) {
                int l = gr[i][0];
                int r = gr[i].back();
                if (A[l - 1] > i && A[r + 1] > i) {
                    //両脇にちっこいのがいない場合
                    cout << 0 << endl;
                    exit(0);
                } else if (A[l - 1] < i && A[r + 1] < i) {
                    //両方共ちっこい場合
                    (ans *= (K - r + l)) %= MOD;
                    rest += r - l + K - 1;
                } else {
                    //かたっぽがちっこい場合
                    rest += r - l;
                }
            } else {
                //等しいね
                int l = gr[i][0];
                int r = gr[i].back();
                if (A[l - 1] > i && A[r + 1] > i) {
                    //しかし　なにもおこらなかった！
                } else if (A[l - 1] < i && A[r + 1] < i) {
                    (ans *= (K - r + l)) %= MOD;
                    rest += r - l + K - 1;
                } else {
                    rest += r - l;
                }
            }
        }
        cout << ans << endl;
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    Solve().solve();


    return 0;
}