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<cstdio>
int l[300005], r[300005];
int a[300005];
int fix[300005];
const long long mod = 998244353;

long long getF(long long n){
    long long res = 1;
    for(long long i = 2; i <= n; i++) res = res*i%mod;
    return res;
}

int getLength(int l,int r,int n){
    if(r>=l) return r-l+1;
    else return n-l+1+r;
}

int stdForm(int u,int n){
    if(u<1) u += n;
    if(u>n) u -= n;
    return u;
}


int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    int p = 1, ok = 1;
    int cnt = 0;
    while(p<=n){
        int np = p, u = a[p];
        while(np+1<=n && a[np+1]==u) np++;
        if(l[u]!=0){
            if(l[u]==1 && np==n)l[u] = p;
            else ok = 0;
        }
        else{
            cnt++;
            l[u] = p, r[u] = np;
        }
        p = np+1;
    }
    if(!ok) printf("0\n");
    else{
        int t = getLength(l[1],r[1],n);
        if(t==n) printf("%lld\n",getF(n));
        else{
            long long ans = 1, blank = 0;
            for(int i = 1; i <= n; i++){
                if(l[i]==0){
                    if(blank==0){
                        ans = 0;
                        break;
                    }
                    else{
                        ans = ans*blank%mod;
                        blank--;
                    }
                }
                else{
                    cnt--;
                    if(getLength(l[i],r[i],n)>t){
                        ans = 0;
                        break;
                    }
                    int left = stdForm(l[i]-1,n), right = stdForm(r[i]+1,n);
                    if(a[left]>i && a[right]>i){ 
                        if(getLength(l[i],r[i],n)!=t){
                            ans = 0;
                            break;
                        }
                        else fix[i] = l[i];
                    }
                    else if(a[left]<i && a[right]<i){
                        int minn = stdForm(r[i]-t+1,n), maxn = stdForm(l[i],n);
                        ans = ans*(long long)getLength(minn,maxn,n)%mod;
                        int next = stdForm(fix[a[left]]+1,n);
                        blank += getLength(next,r[i],n)-1;
                    }
                    else if(a[left]<i){
                        fix[i] = stdForm(r[i]-t+1,n);
                        int next = stdForm(fix[a[left]]+1,n);
                        int upper = stdForm(fix[i]-1,n);
                        if(next!=fix[i]) blank += getLength(next,upper,n);
                    }
                    else{
                        fix[i] = l[i];
                        int next = stdForm(fix[i]+1,n), upper = stdForm(fix[a[right]]-1,n);
                        if(next!=stdForm(fix[a[right]],n)) blank += getLength(next,upper,n);
                    }
                    //makeGood(l[i],r[i],n);
                    if(cnt==0){
                        long long mul = getF(n-i);
                        ans = ans*mul%mod;
                        break;
                    }
                }
                
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}