description: For a permutation p of numbers 1 through n, we define a stair array a as follows: a_i is length of the longest segment of permutation which contains position i and is made of consecutive values in sorted order: [x, x+1, …, y-1, y] or [y, y-1, …, x+1, x] for some x ≤ y. For example, for permutation p = [4, 1, 2, 3, 7, 6, 5] we have a = [1, 3, 3, 3, 3, 3, 3]. 
  
  You are given the stair array a. Your task is to calculate the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353. Note that this number can be equal to zero.
  
  Input
  
  The first line of input contains integer n (1 ≤ n ≤ 10^5) — the length of a stair array a.
  
  The second line of input contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).
  
  Output
  
  Print the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353.
  
  Examples
  
  Input
  
  
  6
  3 3 3 1 1 1
  
  
  Output
  
  
  6
  
  
  Input
  
  
  7
  4 4 4 4 3 3 3
  
  
  Output
  
  
  6
  
  
  Input
  
  
  1
  1
  
  
  Output
  
  
  1
  
  
  Input
  
  
  8
  2 2 2 2 2 2 1 1
  
  
  Output
  
  
  370
  
  
  Input
  
  
  4
  3 2 3 1
  
  
  Output
  
  
  0
solution: #include <bits/stdc++.h>
  using namespace std;
  template <typename A, typename B>
  string to_string(pair<A, B> p);
  template <typename A, typename B, typename C>
  string to_string(tuple<A, B, C> p);
  template <typename A, typename B, typename C, typename D>
  string to_string(tuple<A, B, C, D> p);
  string to_string(const string& s) { return '"' + s + '"'; }
  string to_string(const char* s) { return to_string((string)s); }
  string to_string(bool b) { return (b ? "true" : "false"); }
  string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
      if (!first) {
        res += ", ";
      }
      first = false;
      res += to_string(v[i]);
    }
    res += "}";
    return res;
  }
  template <size_t N>
  string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
      res += static_cast<char>('0' + v[i]);
    }
    return res;
  }
  template <typename A>
  string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto& x : v) {
      if (!first) {
        res += ", ";
      }
      first = false;
      res += to_string(x);
    }
    res += "}";
    return res;
  }
  template <typename A, typename B>
  string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
  }
  template <typename A, typename B, typename C>
  string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
           to_string(get<2>(p)) + ")";
  }
  template <typename A, typename B, typename C, typename D>
  string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
           to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
  }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
  }
  template <typename T>
  T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
      T t = m / a;
      m -= t * a;
      swap(a, m);
      u -= t * v;
      swap(u, v);
    }
    assert(m == 1);
    return u;
  }
  template <typename T>
  class Modular {
   public:
    using Type = typename decay<decltype(T::value)>::type;
    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
      value = normalize(x);
    }
    template <typename U>
    static Type normalize(const U& x) {
      Type v;
      if (-mod() <= x && x < mod())
        v = static_cast<Type>(x);
      else
        v = static_cast<Type>(x % mod());
      if (v < 0) v += mod();
      return v;
    }
    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const {
      return static_cast<U>(value);
    }
    constexpr static Type mod() { return T::value; }
    Modular& operator+=(const Modular& other) {
      if ((value += other.value) >= mod()) value -= mod();
      return *this;
    }
    Modular& operator-=(const Modular& other) {
      if ((value -= other.value) < 0) value += mod();
      return *this;
    }
    template <typename U>
    Modular& operator+=(const U& other) {
      return *this += Modular(other);
    }
    template <typename U>
    Modular& operator-=(const U& other) {
      return *this -= Modular(other);
    }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) {
      Modular result(*this);
      *this += 1;
      return result;
    }
    Modular operator--(int) {
      Modular result(*this);
      *this -= 1;
      return result;
    }
    Modular operator-() const { return Modular(-value); }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                       Modular>::type&
    operator*=(const Modular& rhs) {
      value = normalize(static_cast<int64_t>(value) *
                        static_cast<int64_t>(rhs.value));
      return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value,
                       Modular>::type&
    operator*=(const Modular& rhs) {
      long long q = static_cast<long long>(static_cast<long double>(value) *
                                           rhs.value / mod());
      value = normalize(value * rhs.value - q * mod());
      return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                       Modular>::type&
    operator*=(const Modular& rhs) {
      value = normalize(value * rhs.value);
      return *this;
    }
    Modular& operator/=(const Modular& other) {
      return *this *= Modular(inverse(other.value, mod()));
    }
    friend const Type& abs(const Modular& x) { return x.value; }
    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);
  
   private:
    Type value;
  };
  template <typename T>
  bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
    return lhs.value == rhs.value;
  }
  template <typename T, typename U>
  bool operator==(const Modular<T>& lhs, U rhs) {
    return lhs == Modular<T>(rhs);
  }
  template <typename T, typename U>
  bool operator==(U lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) == rhs;
  }
  template <typename T>
  bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
    return !(lhs == rhs);
  }
  template <typename T, typename U>
  bool operator!=(const Modular<T>& lhs, U rhs) {
    return !(lhs == rhs);
  }
  template <typename T, typename U>
  bool operator!=(U lhs, const Modular<T>& rhs) {
    return !(lhs == rhs);
  }
  template <typename T>
  bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
    return lhs.value < rhs.value;
  }
  template <typename T>
  Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) += rhs;
  }
  template <typename T, typename U>
  Modular<T> operator+(const Modular<T>& lhs, U rhs) {
    return Modular<T>(lhs) += rhs;
  }
  template <typename T, typename U>
  Modular<T> operator+(U lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) += rhs;
  }
  template <typename T>
  Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) -= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator-(const Modular<T>& lhs, U rhs) {
    return Modular<T>(lhs) -= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator-(U lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) -= rhs;
  }
  template <typename T>
  Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) *= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator*(const Modular<T>& lhs, U rhs) {
    return Modular<T>(lhs) *= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator*(U lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) *= rhs;
  }
  template <typename T>
  Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) /= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator/(const Modular<T>& lhs, U rhs) {
    return Modular<T>(lhs) /= rhs;
  }
  template <typename T, typename U>
  Modular<T> operator/(U lhs, const Modular<T>& rhs) {
    return Modular<T>(lhs) /= rhs;
  }
  template <typename T, typename U>
  Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
      if (p & 1) res *= x;
      x *= x;
      p >>= 1;
    }
    return res;
  }
  template <typename T>
  bool IsZero(const Modular<T>& number) {
    return number() == 0;
  }
  template <typename T>
  string to_string(const Modular<T>& number) {
    return to_string(number());
  }
  template <typename U, typename T>
  U& operator<<(U& stream, const Modular<T>& number) {
    return stream << number();
  }
  template <typename U, typename T>
  U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
  }
  constexpr int md = 998244353;
  using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
  vector<Mint> fact(1, 1);
  vector<Mint> inv_fact(1, 1);
  Mint C(int n, int k) {
    if (k < 0 || k > n) {
      return 0;
    }
    while ((int)fact.size() < n + 1) {
      fact.push_back(fact.back() * (int)fact.size());
      inv_fact.push_back(1 / fact.back());
    }
    return fact[n] * inv_fact[k] * inv_fact[n - k];
  }
  template <typename T>
  class NTT {
   public:
    using Type = typename decay<decltype(T::value)>::type;
    static Type md;
    static Modular<T> root;
    static int base;
    static int max_base;
    static vector<Modular<T>> roots;
    static vector<int> rev;
    static void clear() {
      root = 0;
      base = 0;
      max_base = 0;
      roots.clear();
      rev.clear();
    }
    static void init() {
      md = T::value;
      assert(md >= 3 && md % 2 == 1);
      auto tmp = md - 1;
      max_base = 0;
      while (tmp % 2 == 0) {
        tmp /= 2;
        max_base++;
      }
      root = 2;
      while (power(root, (md - 1) >> 1) == 1) {
        root++;
      }
      assert(power(root, md - 1) == 1);
      root = power(root, (md - 1) >> max_base);
      base = 1;
      rev = {0, 1};
      roots = {0, 1};
    }
    static void ensure_base(int nbase) {
      if (md != T::value) {
        clear();
      }
      if (roots.empty()) {
        init();
      }
      if (nbase <= base) {
        return;
      }
      assert(nbase <= max_base);
      rev.resize(1 << nbase);
      for (int i = 0; i < (1 << nbase); i++) {
        rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
      }
      roots.resize(1 << nbase);
      while (base < nbase) {
        Modular<T> z = power(root, 1 << (max_base - 1 - base));
        for (int i = 1 << (base - 1); i < (1 << base); i++) {
          roots[i << 1] = roots[i];
          roots[(i << 1) + 1] = roots[i] * z;
        }
        base++;
      }
    }
    static void fft(vector<Modular<T>>& a) {
      int n = (int)a.size();
      assert((n & (n - 1)) == 0);
      int zeros = __builtin_ctz(n);
      ensure_base(zeros);
      int shift = base - zeros;
      for (int i = 0; i < n; i++) {
        if (i < (rev[i] >> shift)) {
          swap(a[i], a[rev[i] >> shift]);
        }
      }
      for (int k = 1; k < n; k <<= 1) {
        for (int i = 0; i < n; i += 2 * k) {
          for (int j = 0; j < k; j++) {
            Modular<T> x = a[i + j];
            Modular<T> y = a[i + j + k] * roots[j + k];
            a[i + j] = x + y;
            a[i + j + k] = x - y;
          }
        }
      }
    }
    static vector<Modular<T>> multiply(vector<Modular<T>> a,
                                       vector<Modular<T>> b) {
      if (a.empty() || b.empty()) {
        return {};
      }
      int eq = (a == b);
      int need = (int)a.size() + (int)b.size() - 1;
      int nbase = 0;
      while ((1 << nbase) < need) nbase++;
      ensure_base(nbase);
      int sz = 1 << nbase;
      a.resize(sz);
      b.resize(sz);
      fft(a);
      if (eq)
        b = a;
      else
        fft(b);
      Modular<T> inv_sz = 1 / static_cast<Modular<T>>(sz);
      for (int i = 0; i < sz; i++) {
        a[i] *= b[i] * inv_sz;
      }
      reverse(a.begin() + 1, a.end());
      fft(a);
      a.resize(need);
      return a;
    }
  };
  template <typename T>
  typename NTT<T>::Type NTT<T>::md;
  template <typename T>
  Modular<T> NTT<T>::root;
  template <typename T>
  int NTT<T>::base;
  template <typename T>
  int NTT<T>::max_base;
  template <typename T>
  vector<Modular<T>> NTT<T>::roots;
  template <typename T>
  vector<int> NTT<T>::rev;
  template <typename T>
  vector<Modular<T>> inverse(const vector<Modular<T>>& a) {
    assert(!a.empty());
    int n = (int)a.size();
    vector<Modular<T>> b = {1 / a[0]};
    while ((int)b.size() < n) {
      vector<Modular<T>> x(a.begin(), a.begin() + min(a.size(), b.size() << 1));
      x.resize(b.size() << 1);
      b.resize(b.size() << 1);
      vector<Modular<T>> c = b;
      NTT<T>::fft(c);
      NTT<T>::fft(x);
      Modular<T> inv = 1 / static_cast<Modular<T>>((int)x.size());
      for (int i = 0; i < (int)x.size(); i++) {
        x[i] *= c[i] * inv;
      }
      reverse(x.begin() + 1, x.end());
      NTT<T>::fft(x);
      rotate(x.begin(), x.begin() + (x.size() >> 1), x.end());
      fill(x.begin() + (x.size() >> 1), x.end(), 0);
      NTT<T>::fft(x);
      for (int i = 0; i < (int)x.size(); i++) {
        x[i] *= c[i] * inv;
      }
      reverse(x.begin() + 1, x.end());
      NTT<T>::fft(x);
      for (int i = 0; i < ((int)x.size() >> 1); i++) {
        b[i + ((int)x.size() >> 1)] = -x[i];
      }
    }
    b.resize(n);
    return b;
  }
  template <typename T>
  vector<Modular<T>> inverse_old(vector<Modular<T>> a) {
    assert(!a.empty());
    int n = (int)a.size();
    if (n == 1) {
      return {1 / a[0]};
    }
    int m = (n + 1) >> 1;
    vector<Modular<T>> b = inverse(vector<Modular<T>>(a.begin(), a.begin() + m));
    int need = n << 1;
    int nbase = 0;
    while ((1 << nbase) < need) {
      ++nbase;
    }
    NTT<T>::ensure_base(nbase);
    int size = 1 << nbase;
    a.resize(size);
    b.resize(size);
    NTT<T>::fft(a);
    NTT<T>::fft(b);
    Modular<T> inv = 1 / static_cast<Modular<T>>(size);
    for (int i = 0; i < size; ++i) {
      a[i] = (2 - a[i] * b[i]) * b[i] * inv;
    }
    reverse(a.begin() + 1, a.end());
    NTT<T>::fft(a);
    a.resize(n);
    return a;
  }
  template <typename T>
  vector<Modular<T>> operator*(const vector<Modular<T>>& a,
                               const vector<Modular<T>>& b) {
    if (a.empty() || b.empty()) {
      return {};
    }
    if (min(a.size(), b.size()) < 150) {
      vector<Modular<T>> c(a.size() + b.size() - 1, 0);
      for (int i = 0; i < (int)a.size(); i++) {
        for (int j = 0; j < (int)b.size(); j++) {
          c[i + j] += a[i] * b[j];
        }
      }
      return c;
    }
    return NTT<T>::multiply(a, b);
  }
  template <typename T>
  vector<Modular<T>>& operator*=(vector<Modular<T>>& a,
                                 const vector<Modular<T>>& b) {
    return a = a * b;
  }
  template <typename T>
  vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
    if (a.size() < b.size()) {
      a.resize(b.size());
    }
    for (int i = 0; i < (int)b.size(); i++) {
      a[i] += b[i];
    }
    return a;
  }
  template <typename T>
  vector<T> operator+(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c += b;
  }
  template <typename T>
  vector<T>& operator-=(vector<T>& a, const vector<T>& b) {
    if (a.size() < b.size()) {
      a.resize(b.size());
    }
    for (int i = 0; i < (int)b.size(); i++) {
      a[i] -= b[i];
    }
    return a;
  }
  template <typename T>
  vector<T> operator-(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c -= b;
  }
  template <typename T>
  vector<T> operator-(const vector<T>& a) {
    vector<T> c = a;
    for (int i = 0; i < (int)c.size(); i++) {
      c[i] = -c[i];
    }
    return c;
  }
  template <typename T>
  vector<T> operator*(const vector<T>& a, const vector<T>& b) {
    if (a.empty() || b.empty()) {
      return {};
    }
    vector<T> c(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int)a.size(); i++) {
      for (int j = 0; j < (int)b.size(); j++) {
        c[i + j] += a[i] * b[j];
      }
    }
    return c;
  }
  template <typename T>
  vector<T>& operator*=(vector<T>& a, const vector<T>& b) {
    return a = a * b;
  }
  template <typename T>
  vector<T> inverse(const vector<T>& a) {
    assert(!a.empty());
    int n = (int)a.size();
    vector<T> b = {1 / a[0]};
    while ((int)b.size() < n) {
      vector<T> a_cut(a.begin(), a.begin() + min(a.size(), b.size() << 1));
      vector<T> x = b * b * a_cut;
      b.resize(b.size() << 1);
      for (int i = (int)b.size() >> 1; i < (int)min(x.size(), b.size()); i++) {
        b[i] = -x[i];
      }
    }
    b.resize(n);
    return b;
  }
  template <typename T>
  vector<T>& operator/=(vector<T>& a, const vector<T>& b) {
    int n = (int)a.size();
    int m = (int)b.size();
    if (n < m) {
      a.clear();
    } else {
      vector<T> d = b;
      reverse(a.begin(), a.end());
      reverse(d.begin(), d.end());
      d.resize(n - m + 1);
      a *= inverse(d);
      a.erase(a.begin() + n - m + 1, a.end());
      reverse(a.begin(), a.end());
    }
    return a;
  }
  template <typename T>
  vector<T> operator/(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c /= b;
  }
  template <typename T>
  vector<T>& operator%=(vector<T>& a, const vector<T>& b) {
    int n = (int)a.size();
    int m = (int)b.size();
    if (n >= m) {
      vector<T> c = (a / b) * b;
      a.resize(m - 1);
      for (int i = 0; i < m - 1; i++) {
        a[i] -= c[i];
      }
    }
    return a;
  }
  template <typename T>
  vector<T> operator%(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c %= b;
  }
  template <typename T, typename U>
  vector<T> power(const vector<T>& a, const U& b, const vector<T>& c) {
    assert(b >= 0);
    vector<U> binary;
    U bb = b;
    while (bb > 0) {
      binary.push_back(bb & 1);
      bb >>= 1;
    }
    vector<T> res = vector<T>{1} % c;
    for (int j = (int)binary.size() - 1; j >= 0; j--) {
      res = res * res % c;
      if (binary[j] == 1) {
        res = res * a % c;
      }
    }
    return res;
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> init(n);
    for (int i = 0; i < n; i++) {
      cin >> init[i];
    }
    vector<int> a;
    int beg = 0;
    while (beg < n) {
      int len = init[beg];
      if (beg + len > n) {
        cout << 0 << '\n';
        return 0;
      }
      for (int i = beg; i < beg + len; i++) {
        if (init[i] != len) {
          cout << 0 << '\n';
          return 0;
        }
      }
      a.push_back(len);
      beg += len;
    }
    function<vector<vector<Mint>>(int, int)> Solve = [&](int L, int R) {
      if (R - L == 1) {
        vector<vector<Mint>> ret(4);
        if (a[L] > 1) {
          ret[0] = vector<Mint>{1};
          ret[1] = vector<Mint>{0, 2};
          ret[2] = vector<Mint>{1};
          ret[3] = vector<Mint>{0, 2};
        } else {
          ret[0] = vector<Mint>{1};
          ret[1] = vector<Mint>{0, 2};
          ret[2] = vector<Mint>{1};
          ret[3] = vector<Mint>{0, 1};
        }
        return ret;
      }
      int M = (L + R) >> 1;
      auto x = Solve(L, M);
      auto y = Solve(M, R);
      vector<vector<Mint>> ret(4);
      ret[0] = x[0] * y[0] + x[1] * y[2];
      ret[1] = x[0] * y[1] + x[1] * y[3];
      ret[2] = x[2] * y[0] + x[3] * y[2];
      ret[3] = x[3] * y[3] + x[2] * y[1];
      return ret;
    };
    auto ret = Solve(0, (int)a.size());
    auto p1 = ret[3];
    C(n, 0);
    Mint ans = 0;
    for (int k = 1; k < (int)p1.size(); k++) {
      ans += p1[k] * fact[k] * (k % 2 == (int)p1.size() % 2 ? -1 : 1);
    }
    cout << ans << '\n';
    return 0;
  }
  