#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
const ll mod = 998244353;
template <class T, class U>
void add(T& a, U b) {
  a += b;
  if (a >= mod) a -= mod;
}
template <class T, class U>
void sub(T& a, U b) {
  a -= b;
  if (a < 0) a += mod;
}
template <class T, class U>
void mult(T& a, U b) {
  a = ((ll)a * b) % mod;
}
ll modPow(ll a, ll p) {
  ll s = 1;
  while (p) {
    if (p & 1) mult(s, a);
    mult(a, a);
    p >>= 1;
  }
  return s;
}
ll modInv(ll a) { return modPow(a, mod - 2); }
const ll Vmax = 1000010;
ll fact[Vmax], factInv[Vmax], invs[Vmax];
void InitFact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(Vmax); i++) {
    fact[i] = fact[i - 1];
    mult(fact[i], i);
  }
  factInv[Vmax - 1] = modInv(fact[Vmax - 1]);
  for (ll i = Vmax - 2; i >= 0; i--) {
    factInv[i] = factInv[i + 1];
    mult(factInv[i], i + 1);
  }
  for (ll i = Vmax - 1; i >= 1; i--) {
    invs[i] = factInv[i];
    mult(invs[i], fact[i - 1]);
  }
}
ll Choose(ll n, ll k) {
  return ll(fact[n]) * factInv[n - k] % mod * factInv[k] % mod;
}
ll Binom(ll a, ll b) {
  return ll(fact[a + b]) * factInv[a] % mod * factInv[b] % mod;
}
void Impossible() {
  print(0);
  exit(0);
}
signed main() {
  InitFact();
  ll n = read();
  vi a(n);
  for (ll i = ll(0); i < ll(n); i++) a[i] = read() - 1;
  {
    ll head = -1;
    for (ll i = ll(0); i < ll(n); i++)
      if (a[i] != 0) {
        head = i;
        break;
      }
    if (head == -1) {
      print(fact[n]);
      return 0;
    }
    vi tmp;
    for (ll i = ll(head); i < ll(n); i++) tmp.push_back(a[i]);
    for (ll i = ll(0); i < ll(head); i++) tmp.push_back(a[i]);
    a = tmp;
  }
  {
    ll head = -1;
    for (ll i = ll(0); i < ll(n); i++)
      if (a[i] == 0) {
        head = i;
        break;
      }
    if (head == -1) {
      Impossible();
    }
    vi tmp;
    for (ll i = ll(head); i < ll(n); i++) tmp.push_back(a[i]);
    for (ll i = ll(0); i < ll(head); i++) tmp.push_back(a[i]);
    a = tmp;
  }
  cerrDummy << a << endl;
  const pi e(-1, -1);
  vector<pi> rng(n, e);
  for (ll i = ll(0); i < ll(n); i++) {
    if (rng[a[i]] == e) {
      rng[a[i]] = pi(i, i + 1);
    } else {
      rng[a[i]].second = i + 1;
    }
  }
  cerrDummy << rng << endl;
  {
    ll len = 0;
    for (ll i = ll(0); i < ll(n); i++) len += rng[i].second - rng[i].first;
    if (len != n) {
      Impossible();
    }
  }
  ll k = rng[0].second - rng[0].first;
  cerrDummy << k << endl;
  if (k == n) {
    print(fact[n]);
    return 0;
  }
  {
    for (ll i = ll(0); i < ll(n); i++) {
      if (rng[i].second - rng[i].first > k) {
        Impossible();
      }
    }
  }
  vi cur(n, -1);
  vi dec(n, 0);
  for (ll i = ll(0); i < ll(n); i++)
    if (rng[i] != e) {
      ll x = rng[i].first;
      ll y = rng[i].second;
      if (x - 1 >= 0 && a[x - 1] > i) {
        for (ll j = x; j < x + k && j < n && cur[j] == -1; j++) cur[j] = i;
        dec[i] = 1;
      }
      if (y < n && a[y] > i) {
        for (ll j = y - 1; j >= y - k && j >= 0 && cur[j] == -1; j--)
          cur[j] = i;
        dec[i] = 1;
      }
    }
  cerrDummy << cur << endl;
  cerrDummy << dec << endl;
  {
    for (ll i = ll(0); i < ll(n); i++) {
      if (cur[i] == -1) {
        if (dec[a[i]]) Impossible();
      } else {
        if (cur[i] != a[i]) Impossible();
      }
    }
  }
  ll rem = n;
  for (ll i = ll(0); i < ll(n); i++) {
    if (dec[i]) {
      rem--;
    } else if (rng[i] != e) {
      rem -= k - 1 + (rng[i].second - rng[i].first);
    }
  }
  ll ans = 1;
  for (ll i = ll(0); i < ll(n); i++)
    if (!dec[i]) {
      ll len = rng[i].second - rng[i].first;
      cerrDummy << i << " " << rem << endl;
      if (len > 0) {
        cerrDummy << i << " " << len << endl;
        mult(ans, k + 1 - len);
        rem += k - 1 + len - 1;
      } else {
        mult(ans, rem);
        rem--;
      }
    }
  print(ans);
}
