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 <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<int> a, ai(n); REP(i, n) cin >> ai[i];

  // 1 を先頭にもっていく
  if (ai.front() == 1 && ai.back() == 1) {
    int idx;
    for (idx = n - 1; idx >= 0; --idx) {
      if (ai[idx] != 1) break;
    }
    FOR(i, idx + 1, n) a.emplace_back(ai[i]);
    REP(i, idx + 1) a.emplace_back(ai[i]);
  } else {
    int idx;
    for (idx = 0; idx < n; ++idx) {
      if (ai[idx] == 1) break;
    }
    FOR(i, idx, n) a.emplace_back(ai[i]);
    REP(i, idx) a.emplace_back(ai[i]);
  }

  // 1 がない場合
  if (a[0] != 1) {
    cout << 0 << '\n';
    return 0;
  }
  int len = -1; // 1 の長さ
  REP(i, n) {
    if (a[i] != 1) {
      len = i;
      break;
    }
  }
  // 1 のみの場合
  if (len == -1) {
    long long ans = 1;
    FOR(i, 1, n + 1) (ans *= i) %= MOD;
    cout << ans << '\n';
    return 0;
  }

  // exist[i] = {f, s} のとき
  // i は 区間 [f, f + s) を形成している
  vector<pair<int, int> > exist(n + 1, {0, 0});
  exist[1] = {0, len};
  for (int i = len; i < n;) {
    if (exist[a[i]].second > 0) { // 既に区間が存在している場合
      cout << 0 << '\n';
      return 0;
    }
    exist[a[i]].first = i;
    int j = i;
    while (j < n && a[j] == a[i]) ++j;
    exist[a[i]].second = j - i;
    if (exist[a[i]].second > len) { // 1 より長い区間はない
      cout << 0 << '\n';
      return 0;
    }
    i = j;
  }

  long long ans = 1;
  int can = 0; // 現れていない数を置くことのできる位置の数
  // {i : A[i] > 今までに見た数}
  // {i : A[i] <= 今までに見た数 && 現れていない数を置くことができない位置 && まだ何も置かれていない位置}
  set<int> bigger, remain;
  REP(i, n) bigger.emplace(i);
  FOR(i, 1, n + 1) { // 小さい数から順に見ていく
    if (exist[i].second == 0) { // A に現れていない場合
      (ans *= can--) %= MOD;
    } else {
      if ((exist[i].first == 0 || a[exist[i].first - 1] > i) && (exist[i].first + exist[i].second < n && a[exist[i].first + exist[i].second] > i)) { // 大きい数に挟まれている
        if (exist[i].second != len) {
          cout << 0 << '\n';
          return 0;
        }
      }
      if ((exist[i].first - 1 >= 0 && a[exist[i].first - 1] < i) && (exist[i].first + exist[i].second == n || a[exist[i].first + exist[i].second] < i)) { // 小さい数に挟まれている
        // [i の末尾から (len - 1) 個前, i の先頭] が p において i となる可能性がある
        // A におけるこの区間には必ず i 以下の数が並ぶ
        // もし i より大きい数 (x とする) が存在するならば
        // x < y > z となる部分が存在するが y の長さは len でなければならない
        (ans *= len - exist[i].second + 1) %= MOD;
      }
      FOR(j, exist[i].first, exist[i].first + exist[i].second) {
        bigger.erase(j);
        remain.emplace(j);
      }
      // 新しく can に入る位置を調べる
      // *it より前は i を見ることによって加わることがない
      auto it = remain.lower_bound(exist[i].first - len + 1);
      while (it != remain.end() && *it < exist[i].first + exist[i].second) {
        auto nearest = bigger.lower_bound(*it);
        if (nearest == bigger.end() || *nearest - *it >= len) {
          ++can;
          it = remain.erase(it);
        } else {
          it = remain.lower_bound(*nearest);
        }
      }
      --can;
    }
  }
  cout << ans << '\n';
  return 0;
}