#include <bits/stdc++.h>
using namespace std;
int n;
int a[300005];
vector<int> pos[300005];
long long ans = 1;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
    pos[a[i]].push_back(i);
  }
  for (int i = 0; i < n; i++) sort(pos[i].begin(), pos[i].end());
  int a = pos[0].size();
  if (a == 0) {
    puts("0");
    return 0;
  }
  if (a == n) {
    for (int i = 1; i <= n; i++) ans = ans * 1LL * i % 998244353;
    cout << ans << endl;
    return 0;
  }
  vector<int> vec;
  for (int i = 1; i < pos[0].size(); i++) {
    vec.push_back(pos[0][i] - pos[0][i - 1]);
  }
  int sum = 0, cnt = 0, beg = pos[0][0];
  for (int i = 0; i < vec.size(); i++) {
    if (vec[i] != 1) {
      cnt++;
      beg = pos[0][i + 1];
    }
    sum += vec[i];
  }
  if (cnt >= 2 && (cnt == 1 && sum != n - 1)) {
    puts("0");
    return 0;
  }
  int zan = 0;
  set<pair<int, int> > S;
  int lb = (beg + a) % n;
  int ub = (beg + n - 1) % n;
  if (lb > ub) ub += n;
  S.insert(make_pair(lb, ub));
  int X = lb, Y = ub;
  for (int i = 1; i < n; i++) {
    if (pos[i].empty()) {
      if (zan == 0) {
        puts("0");
        return 0;
      }
      ans = ans * 1LL * zan % 998244353;
      zan--;
      continue;
    }
    if (pos[i].size() > a) {
      puts("0");
      return 0;
    }
    vector<int> vec;
    for (int ii = 1; ii < pos[i].size(); ii++) {
      vec.push_back(pos[i][ii] - pos[i][ii - 1]);
    }
    int sum = 0, cnt = 0, beg = pos[i][0];
    for (int i = 0; i < vec.size(); i++) {
      if (vec[i] != 1) {
        cnt++;
        beg = pos[0][i + 1];
      }
      sum += vec[i];
    }
    if (cnt >= 2 && (cnt == 1 && sum != n - 1)) {
      puts("0");
      return 0;
    }
    int L = beg;
    int R = (beg + pos[i].size() - 1) % n;
    if (L > R) R += n;
    if (R < X) {
      L += n;
      R += n;
    }
    vector<pair<int, int> > cand;
    set<pair<int, int> >::iterator it = S.lower_bound(make_pair(L, R));
    if (it != S.end()) {
      cand.push_back(*it);
      it++;
      if (it != S.end()) {
        cand.push_back(*it);
      }
      it--;
    }
    if (it != S.begin()) {
      it--;
      cand.push_back(*it);
      it++;
    }
    for (int x = 0; x < cand.size(); x++) S.erase(S.find(cand[x]));
    int C = 0;
    for (int x = 0; x < cand.size(); x++) {
      int mn = min(cand[x].second, R);
      int mx = max(cand[x].first, L);
      if (mn - mx + 1 <= 0) {
        S.insert(cand[x]);
      } else {
        C++;
        if (cand[x].first <= L && R <= cand[x].second) {
          if (cand[x].first == L && cand[x].second == R) {
            ans = ans * 1LL * (a - (R - L)) % 998244353;
            zan += a - (R - L) - 1;
          } else if (cand[x].first == L) {
            zan += R - cand[x].first;
            S.insert(make_pair(R + 1, cand[x].second));
          } else if (cand[x].second == R) {
            zan += cand[x].second - L;
            S.insert(make_pair(cand[x].first, L - 1));
          } else {
            if (cand[x].second - cand[x].first + 1 != a) {
              puts("0");
              return 0;
            }
            S.insert(make_pair(cand[x].first, L - 1));
            S.insert(make_pair(R + 1, cand[x].second));
          }
        } else {
          puts("0");
          return 0;
        }
      }
    }
    if (S.size() == 0) {
      int zan = n - 1 - i;
      for (int i = 1; i <= zan; i++) ans = ans * 1LL * i % 998244353;
      cout << ans << endl;
      return 0;
    }
    assert(C == 1);
  }
  cout << ans << endl;
}
