#include <bits/stdc++.h>
using namespace std;
int a[300100];
int mi[300100], le[300100];
int rm[300100];
vector<int> num, len;
vector<pair<int, int> > p;
vector<int> v;
vector<long long> zyo, rz;
long long mo = 998244353;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a;
  x = 1;
  y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
long long invMod(long long a, long long m) {
  long long x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;
  return 0;
}
long long calp(int a, int b) {
  if (a < b) return 0;
  return (zyo[a] * rz[a - b]) % mo;
}
int main() {
  zyo.push_back(1);
  for (int i = 0; i < 300200; i++) zyo.push_back((zyo[i] * (i + 1)) % mo);
  for (int i = 0; i < 300200; i++) rz.push_back(invMod(zyo[i], mo));
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  for (int i = 0; i < n; i++) mi[i] = n + 10;
  for (int i = 0; i < n; i++) mi[a[i]] = min(mi[a[i]], i);
  for (int i = 0; i < n; i++) {
    if (mi[i] != 0) continue;
    int t = n - 1;
    while (t >= 0 && a[t] == i) t--;
    mi[i] = (t + 1) % n;
  }
  for (int i = 0; i < n; i++) {
    rm[mi[i]] = i;
    le[i] = 0;
    if (mi[i] > n) {
      continue;
    }
    while (le[i] < n && a[(mi[i] + le[i]) % n] == i) le[i]++;
  }
  int sl = 0;
  for (int i = 0; i < n; i++) sl += le[i];
  if (sl != n) {
    cout << 0 << endl;
    return 0;
  }
  if (mi[0] > n) {
    cout << 0 << endl;
    return 0;
  }
  int now = 0;
  while (1) {
    num.push_back(now);
    len.push_back(le[now]);
    now = rm[(mi[now] + le[now]) % n];
    if (now == 0) break;
  }
  int m = num.size();
  long long out = 1;
  for (int i = 1; i < m; i++) {
    if (num[i] > 0 && len[i] > len[0]) {
      cout << 0 << endl;
      return 0;
    }
    if (len[i] < len[0]) {
      if (num[i] < num[i - 1] && i < m - 1 && num[i] < num[i + 1]) {
        cout << 0 << endl;
        return 0;
      } else if (num[i] > num[i - 1] && (i >= m - 1 || num[i] > num[i + 1])) {
        out *= len[0] - len[i] + 1;
        out %= mo;
      }
    }
  }
  int tu = len[0];
  for (int i = 0; i < m - 1; i++) {
    if (len[i + 1] < tu) {
      if (num[i + 1] > num[i]) len[i] = len[i + 1], len[i + 1] = tu;
    }
  }
  for (int i = 0; i < m; i++) {
    int bo = num[i];
    if (i < m - 1) bo = max(bo, num[i + 1]);
    p.push_back(make_pair(bo, len[i] - 1));
    v.push_back(num[i]);
  }
  sort(p.begin(), p.end());
  reverse(p.begin(), p.end());
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  int used = 0, i1 = 0, i2 = 0;
  while (i1 < m) {
    while (i2 < m && v[i2] > p[i1].first) {
      i2++;
      used++;
    }
    out *= calp(n - p[i1].first - used - 1, p[i1].second);
    out %= mo;
    used += p[i1].second;
    i1++;
  }
  cout << out << endl;
}
