#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6, P = 998244353;
int n, s, k, fa[N], sz[N], a[N], lm[N], rm[N], st[N], l[N], r[N];
vector<int> G[N];
int getfa(int u) { return fa[u] == u ? u : fa[u] = getfa(fa[u]); }
int calc(int x) { return x == n ? n : max(x - (k - 1), 0); }
void merge(int x, int y) {
  x = getfa(x), y = getfa(y);
  if (x == y) return;
  s += calc(sz[x] + sz[y]) - calc(sz[x]) - calc(sz[y]);
  fa[y] = x, sz[x] += sz[y];
}
bool check(int x) {
  int m = G[x].size();
  if (!m) return true;
  if (G[x][0] == 1 || G[x][m - 1] == n) {
    int c = 0, t = n;
    while (a[t] == x) ++c, --t;
    l[x] = t;
    t = 1;
    while (a[t] == x) ++c, ++t;
    r[x] = t;
    return c == m;
  } else {
    int c = 0, t = G[x][0];
    while (a[t] == x) ++c, ++t;
    l[x] = G[x][0] - 1, r[x] = t;
    return c == m;
  }
}
int pre(int i) { return i == 1 ? n : i - 1; }
int suc(int i) { return i == n ? 1 : i + 1; }
int main() {
  int c1 = 0;
  scanf("%d", &n);
  for (int i = 1, iend = n; i <= iend; ++i) {
    scanf("%d", &a[i]);
    G[a[n + i] = a[i]].push_back(i);
  }
  if (G[1].size() == n) {
    int ans = 1;
    for (int i = 2, iend = n; i <= iend; ++i) ans = (long long)ans * i % P;
    printf("%d\n", ans);
    return 0;
  }
  for (int i = 1, iend = n; i <= iend; ++i)
    if (!check(i)) {
      printf("0\n");
      return 0;
    }
  int tp = 0;
  for (int i = 1, iend = 2 * n; i <= iend; ++i) {
    while (tp && a[st[tp]] < a[i]) --tp;
    lm[i] = st[tp] ? st[tp] : -n;
    st[++tp] = i;
  }
  tp = 0;
  for (int i = 2 * n, iend = 1; i >= iend; --i) {
    while (tp && a[st[tp]] < a[i]) --tp;
    rm[i] = st[tp] ? st[tp] : 3 * n;
    st[++tp] = i;
  }
  int ans = 1;
  k = G[1].size();
  for (int i = 1, iend = n; i <= iend; ++i) fa[i] = i, sz[i] = 0;
  for (int i = 1, iend = n; i <= iend; ++i) {
    int m = G[i].size();
    if (m) {
      if (a[l[i]] < i && a[r[i]] < i) {
        if (m > k) {
          printf("0\n");
          return 0;
        }
        ans = (long long)ans * (k - m + 1) % P;
      } else if (a[l[i]] > i) {
        if (rm[r[i]] + (l[i] > r[i] ? n : 0) <= l[i] + k) {
          printf("0\n");
          return 0;
        }
      } else if (a[r[i]] > i) {
        if (lm[l[i]] >= r[i] - k + (l[i] > r[i] ? n : 0)) {
          printf("0\n");
          return 0;
        }
      } else if (a[l[i]] > i && a[r[i]] > i && m != k) {
        printf("0\n");
        return 0;
      }
    } else {
      if (s < i) {
        printf("0\n");
        return 0;
      };
      ans = (long long)ans * (s - i + 1) % P;
    }
    for (int j = 0, jend = m; j < jend; ++j) sz[G[i][j]] = 1;
    for (int j = 0, jend = m; j < jend; ++j) {
      int t = G[i][j];
      if (a[pre(t)] <= i) merge(pre(t), t);
      if (a[suc(t)] < i) merge(suc(t), t);
    }
  }
  printf("%d\n", ans);
  return 0;
}
