#include <bits/stdc++.h>
using namespace std;
signed long long mo = 998244353;
int N;
int B[1303030];
int A[1303030];
vector<int> P[303030];
int L[303030];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N;
  for (i = 0; i < (N); i++) {
    cin >> A[i];
    A[i]--;
  }
  if (count(A, A + N, 0) == 0) return (void)printf("0\n");
  if (count(A, A + N, 0) == N) {
    signed long long ret = 1;
    for (i = 0; i < (N); i++) ret = ret * (i + 1) % mo;
    cout << ret << endl;
    return;
  }
  for (i = 0; i < (N); i++)
    if (A[i] == 0 && A[(i + N - 1) % N] > 0) {
      for (j = 0; j < (2 * N); j++) B[j] = A[(i + j) % N];
      for (j = 0; j < (2 * N); j++) A[j] = B[j];
      for (j = 0; j < (N); j++) P[A[j]].push_back(j);
      break;
    }
  signed long long ret = 1;
  set<int> empty, unused;
  int numfree = 0;
  empty.insert(4 * N);
  for (i = 0; i < (N); i++) empty.insert(i), empty.insert(i + N);
  for (i = 0; i < (N); i++) {
    L[i] = P[i].size();
    if (L[i] > L[0]) return (void)printf("0\n");
    if (L[i] == 0) {
      ret = ret * numfree % mo;
      numfree--;
    } else {
      if (P[i][0] + L[i] - 1 != P[i].back()) return (void)printf("0\n");
      for (auto& p : P[i]) {
        empty.erase(p);
        empty.erase(N + p);
        unused.insert(p);
      }
      x = P[i][0];
      if (A[x + N - 1] > i && A[x + L[i]] > i && L[i] != L[0])
        return (void)printf("0\n");
      if (A[x + N - 1] < i && A[x + L[i]] < i)
        ret = ret * (L[0] - L[i] + 1) % mo;
      while (1) {
        auto it = unused.lower_bound(P[i][0] - (L[0] - 1));
        if (it == unused.end()) break;
        auto it2 = empty.lower_bound(*it);
        if (*it2 - *it < L[0]) break;
        numfree++;
        unused.erase(it);
      }
      numfree--;
    }
  }
  assert(0);
  cout << ret << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}
