Problem: You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

* For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

* 1 \leq N \leq 3 × 10^5
* 1 \leq A_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1
:
A_N


Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Examples

Input

3
1
2
1


Output

2


Input

5
3
1
4
1
5


Output

0


Input

8
4
4
4
1
1
1
2
2


Output

24


Input

6
1
1
6
2
2
2


Output

0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(Int k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  static vector<Mint> fact,finv,invs;
  
  static void init(Int n){
    if(n+1<=(signed)fact.size()) return;
    fact.assign(n+1,1);
    finv.assign(n+1,1);
    invs.assign(n+1,1);
    
    for(Int i=1;i<=n;i++) fact[i]=fact[i-1]*Mint(i);
    finv[n]=Mint(1)/fact[n];
    for(Int i=n;i>=1;i--) finv[i-1]=finv[i]*Mint(i);
    for(Int i=1;i<=n;i++) invs[i]=finv[i]*fact[i-1];
  }
  
  static Mint P(Int n,Int k){
    if(n<k||k<0) return Mint(0);
    init(n);
    return fact[n]*finv[n-k];
  }
};
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::fact = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::finv = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::invs = vector<Mint<T, MOD> >();

//INSERT ABOVE HERE
using M = Mint<Int, 998244353>;
signed main(){
  Int n;
  cin>>n;
  deque<Int> d(n);
  for(Int i=0;i<n;i++) cin>>d[i];

  auto NG=[](){cout<<0<<endl;exit(0);};

  if(count(d.begin(),d.end(),1)==0) NG();
  if(count(d.begin(),d.end(),1)==n){
    cout<<M::P(n,n).v<<endl;
    return 0;
  }
  
  if(d[0]==1){
    while(d.back()==1){
      d.pop_back();
      d.push_front(1);
    }
  }else{
    while(d[0]!=1){
      Int k=d[0];
      d.pop_front();
      d.push_back(k);        
    }
  }

  vector<Int> a(d.begin(),d.end());

  //for(Int x:a) cout<<x<<" ";
  //cout<<endl;

  map<Int, Int> ls,rs;
  for(Int i=0;i<n;i++) ls[a[i]]=rs[a[i]]=i;
  for(Int i=0;i<n;i++){
    chmin(ls[a[i]],i);
    chmax(rs[a[i]],i);
  }

  {
    vector<Int> b(a);
    b.erase(unique(b.begin(),b.end()),b.end());
    if(b.size()!=ls.size()) NG();
  }

  Int len=rs[1]-ls[1]+1;
  for(Int i=0;i<n;i++)
    if(rs[a[i]]-ls[a[i]]+1>len) NG();

  //assert(0);
  M ans(1);
  
  set<Int> s;
  s.emplace(0);
  s.emplace(n);

  Int cnt=0;
  for(Int i=2;i<=n;i++){
    //cout<<i<<"::::"<<ans.v<<endl;
    if(!ls.count(i)){
      ans*=M(cnt);
      cnt--;
      continue;      
    }
    M way(0);
    Int pr=*--s.upper_bound(ls[i]);
    Int nx=*  s.upper_bound(ls[i]);
    //cout<<pr<<"<-"<<ls[i]<<" "<<rs[i]<<"->"<<nx<<endl;
    if(rs[i]+1<nx){      
      if(pr+len<ls[i]&&ls[i]!=rs[i]-len+1) NG();
      way+=M(1);
      s.emplace(rs[i]-len+1);      
      if(pr+len>=ls[i]) cnt+=(rs[i]-len+1)-(pr+1);
    }else{
      way+=M(1);
      s.emplace(ls[i]);
      cnt+=nx-(ls[i]+1);
      
      if(pr+len>=ls[i]){
        cnt+=ls[i]-(pr+1);
        
        Int x=max(pr+1,rs[i]-len+1);
        Int y=min(pr+len-1,ls[i]-1);
        if(x<=y) way+=M(y-x+1);
      }
    }
    //cout<<i<<":"<<way.v<<endl;
    ans*=way;
  }
  //assert(0);
  cout<<ans.v<<endl;
  return 0;
}