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;
typedef long long ll;
const int N=3e5+5,mod=998244353;
int n,tot,sum[N],must[N],a[N],b[N],vis[N],vv[N];
int t[N<<2];
void fix(int l,int r,int k,int x,int y,int v)
{
    if(r<x||l>y) return;
    if(l>=x&&r<=y){t[k]=max(t[k],v);return;}
    int m=l+r>>1;
    fix(l,m,k<<1,x,y,v);fix(m+1,r,k<<1|1,x,y,v);
}
void push(int l,int r,int k)
{
    if(l==r){b[l]=t[k];return;}
    int m=l+r>>1;
    t[k<<1]=max(t[k<<1],t[k]);
    t[k<<1|1]=max(t[k<<1|1],t[k]);
    push(l,m,k<<1);push(m+1,r,k<<1|1);
}
void solve(int l,int r,int v)
{
    if(l>=1&&r<=n) fix(1,n,1,l,r,v);
    else if(l<1&&r>n) fix(1,n,1,1,n,v);
    else if(l<1)
    {
        fix(1,n,1,1,r,v);
        l--;
        fix(1,n,1,n-l+1,n,v);
    }
    else if(r>n)
    {
        fix(1,n,1,l,n,v);
        r-=n;
        fix(1,n,1,1,r,v);
    }
}
pair<int,int>pi[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int p=0;
    bool flag=true;
    for(int i=n;i>=1;i--)
    if(a[i]==1&&a[i-1]!=1){p=i;break;}
    if(!p) flag=false;
    for(int i=p;i<=n;i++) b[++tot]=a[i];
    for(int i=1;i<p;i++) b[++tot]=a[i];
    for(int i=1;i<=n;i++)
    {
        if(b[i]!=b[i-1]) vis[b[i]]++;
        if(pi[b[i]].first&&i>=pi[b[i]].first&&i<=pi[b[i]].second) vv[b[i]]++;
    }
    for(int i=1;i<=n;i++)
        if(vis[i]>=2) flag=false;
    int len=0;
    for(int i=1;i<=n;i++)
        if(b[i]==1) len++;
    else break;
    if(len==n)
    {
        ll ans=1;
        for(int i=1;i<=n;i++) ans=ans*i%mod;
        printf("%lld\n",ans);
        return 0;
    }
    int t=1;
    for(int i=2;i<=n;i++)
    {
        if(b[i]==b[i-1]) t++;
        else
        {
            if(t>1)
                solve(i-(t-1),i-1,b[i-1]+1);
            solve(i-len,i-t,b[i-1]);
            pi[b[i-1]]={i-len,i-t};
            solve(i-t-len+1,i-len-1,b[i-1]+1);
            t=1;
        }
        if(t>len) flag=false;
    }
    if(t>1)
        solve(n+1-(t-1),n+1-1,b[n]+1);
    solve(n+1-len,n+1-t,b[n]);
    pi[b[n]]={n+1-len,n+1-t};
    solve(n+1-t-len+1,n+1-len-1,b[n]+1);
    for(int i=1;i<=n;i++) must[b[i]]=true;
    push(1,n,1);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) sum[i]=1;
    for(int i=1;i<=n;i++)
    {
        vis[b[i]]++;
        if(must[b[i]]&&i>=pi[b[i]].first&&i<=pi[b[i]].second) vv[b[i]]++;
    }
    ll ans=1;
    //for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",sum[i]);
    //for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",b[i]);
    //for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",must[i]);
    for(int i=n+1;i>=1;i--)
    {
        if(must[i])
        {
            if(!sum[i]||!vv[i]||!vis[i]) {flag=false;break;}
            ans=ans*vv[i]%mod;
            sum[i]--;vis[i]--;
        }
        sum[i]+=sum[i+1];
        while(vis[i])
        {
            if(!sum[i]) {flag=false;break;}
            ans=ans*sum[i]%mod;
            sum[i]--;
            vis[i]--;
        }
    }
    if(!flag) ans=0;
    printf("%lld\n",ans);
}