#include <bits/stdc++.h>
using namespace std;
void mmin(long long &a, long long b) { a = min(a, b); }
void mmax(long long &a, long long b) { a = max(a, b); }
void sor(vector<long long> &v) { sort(v.begin(), v.end()); }
signed main() {
  long long p = 998244353;
  long long n;
  cin >> n;
  vector<long long> a(n);
  long long x = -1;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  vector<long long> qun(n);
  vector<long long> qko(n, 0);
  long long si = 0;
  qun[0] = a[0];
  qko[0] = 1;
  for (long long i = 1; i < n; i++) {
    if (a[i] != qun[si]) si++;
    qun[si] = a[i];
    qko[si]++;
  }
  if (qun[0] == qun[si] and si != 0) {
    qko[0] += qko[si];
    si--;
  }
  vector<long long> un(si + 1);
  vector<long long> ko(si + 1);
  vector<long long> po(n, -1);
  for (long long i = 0; i <= si; i++) {
    un[i] = qun[i];
    ko[i] = qko[i];
    po[un[i]] = i;
  }
  vector<long long> mu = un;
  sor(mu);
  long long db = 0;
  for (long long i = 0; i < si; i++) {
    if (mu[i] == mu[i + 1]) db = 1;
  }
  long long mak1 = mu[si];
  if (db == 1)
    cout << 0 << endl;
  else {
    long long ans = 1;
    vector<long long> ah(si + 1, 0);
    long long ex = 0;
    if (po[0] == -1) {
      cout << 0 << endl;
      return 0;
    }
    long long mes = ko[po[0]];
    for (long long i = 0; i < n; i++) {
      long long po1 = po[i];
      if (po1 == -1) {
        ans *= ex;
        ans = ans % p;
        ex--;
      } else {
        long long ko1 = ko[po1];
        if (ko1 > mes) {
          ans = 0;
        }
        long long xx = ah[(po1 + 1) % (si + 1)] + ah[(po1 + si) % (si + 1)];
        if (xx == 0) {
          if (ko1 == n) {
            ex = n - 1;
            ans *= n;
          }
          if (ko1 != mes) {
            ans = 0;
          }
        }
        if (xx == 1) {
          ex += ko1 - 1;
        }
        if (xx == 2) {
          if (i != mak1) {
            ex += ko1 + mes;
          } else {
            ex = n - i - 1;
          }
          ans *= (mes - ko1 + 1);
          ans = ans % p;
        }
        ah[po1] = 1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
