#include <bits/stdc++.h>
using namespace std;
struct UF {
  int par[300005], rank[300005];
  void init(int n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      rank[i] = 0;
    }
  }
  int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int l, int r) { par[l] = r; }
  bool same(int x, int y) { return find(x) == find(y); }
};
UF left, right;
int A[300005];
vector<int> vec[300005];
bool use[300005];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    A[i]--;
    vec[A[i]].push_back(i);
  }
  long long int ret = 1;
  int cnt = 0;
  if (vec[0].size() == n) {
    for (int i = 1; i <= n; i++) ret = ret * (long long int)i % 998244353;
    printf("%lld\n", ret);
    return 0;
  }
  int k = vec[0].size();
  left.init(n + 2);
  right.init(n + 2);
  int zan = n;
  for (int i = 0; i < n; i++) {
    if (vec[i].empty()) {
      if (cnt == i) {
        ret = 0;
        break;
      }
      ret = ret * (long long int)(cnt - i) % 998244353;
    } else {
      for (int j = 0; j < vec[i].size(); j++) {
        int v = vec[i][j];
        if (zan > 1) {
          zan--;
          use[v] = true;
          if (use[(v + 1) % n]) {
            right.unite(v, (v + 1) % n);
            left.unite((v + 1) % n, v);
          }
          if (use[(v - 1 + n) % n]) {
            right.unite((v - 1 + n) % n, v);
            left.unite(v, (v - 1 + n) % n);
          }
          int l = left.find(v), r = right.find(v);
          int vl = v - l, vr = r - v;
          if (vl < 0) vl += n;
          if (vr < 0) vr += n;
          cnt -= max(0, vl - k + 1);
          cnt -= max(0, vr - k + 1);
          cnt += max(0, vl + vr + 1 - k + 1);
        } else {
          zan--;
          cnt = n;
        }
      }
      if (zan == 0) {
        sort(vec[i].begin(), vec[i].end());
        int all = 0;
        for (int j = 0; j < vec[i].size(); j++) {
          int v = vec[i][j];
          int u = vec[i][(j + 1) % vec[i].size()];
          int L = u - v - 1;
          if (L < 0) L += n;
          all += max(0, L - (n - k) + 1);
        }
        ret = ret * (long long int)all % 998244353;
      } else {
        bool up = true;
        for (int j = 0; j < vec[i].size(); j++) {
          int v = vec[i][j], u = vec[i][0];
          if (!right.same(v, u)) {
            up = false;
            break;
          }
        }
        if (!up) {
          ret = 0;
          break;
        }
        int l = left.find(vec[i][0]), r = right.find(vec[i][0]);
        int L = r - l + 1;
        if (L < 0) L += n;
        int vl = L, vr = L;
        for (int j = 0; j < vec[i].size(); j++) {
          int v = vec[i][j];
          int len = v - l;
          if (len < 0) len += n;
          vl = min(vl, len);
          len = r - v;
          if (len < 0) len += n;
          vr = min(vr, len);
        }
        int c = L - vl - vr;
        if (c > k) {
          ret = 0;
          break;
        }
        int nm = k - c + 1;
        nm = min(nm, vl + 1);
        nm = min(nm, vr + 1);
        ret = ret * (long long int)nm % 998244353;
      }
    }
  }
  printf("%lld\n", ret);
  return 0;
}
