#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
const int inf = INT_MAX / 2;
const long long 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;
}
long long mo = 998244353;
int N, A[1201010], B[1201010];
vector<int> P[301010];
int L[301010];
long long solve() {
  if (count(A, A + N, 0) == 0) return 0;
  if (count(A, A + N, 0) == N) {
    long long res = 1;
    for (int i = 0; i < N; i++) res *= i + 1, res %= mo;
    return res;
  }
  for (int i = 0; i < N; i++)
    if (A[i] == 0 and 0 < A[(i - 1 + N) % N]) {
      for (int j = 0; j < 2 * N; j++) B[j] = A[(i + j) % N];
      for (int j = 0; j < 2 * N; j++) A[j] = B[j];
      for (int j = 0; j < N; j++) P[A[j]].push_back(j);
    }
  long long res = 1;
  set<int> empty, unused;
  int numfree = 0;
  empty.insert(4 * N);
  for (int i = 0; i < N; i++) empty.insert(i), empty.insert(i + N);
  for (int i = 0; i < N; i++) {
    L[i] = P[i].size();
    if (L[0] < L[i]) return 0;
    if (L[i] == 0) {
      res *= numfree;
      res %= mo;
      numfree--;
    } else {
      if (P[i][0] + L[i] - 1 != P[i].back()) return 0;
      for (auto &p : P[i]) {
        empty.erase(p);
        empty.erase(p + N);
        unused.insert(p);
      }
      int x = P[i][0];
      if (A[x + N - 1] > i && A[x + L[i]] > i && L[i] != L[0]) return 0;
      if (A[x + N - 1] < i && A[x + L[i]] < i)
        res = res * (L[0] - L[i] + 1) % mo;
      auto it = unused.lower_bound(P[i][0] - (L[0] - 1));
      while (it != unused.end() && *it <= P[i].back()) {
        auto it2 = empty.lower_bound(*it);
        if (*it2 - *it < L[0]) {
          it = unused.lower_bound(*it2);
        } else {
          numfree++;
          it = unused.erase(it);
        }
      }
      numfree--;
    }
  }
  return res;
}
void _main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i]--;
  }
  cout << solve() << endl;
}
