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>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int mod = 998244353;
int a[600000];
int f[300001];

int main() {
    int n, p = -1, c, num = 0, i, j, k;
    long long ans = 1;
    vector <pair<int, pair<int, int>>> v;
    set <pair<int, int>> s;
    set <pair<int, int>>::iterator it, it2;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (i = n; i < n * 2; i++) a[i] = a[i - n];
    
    if (a[0] == 1) {
        p = n;
        
        for (i = n - 1; i >= 0; i--) {
            if (a[i] != 1) break;
            p--;
        }
    } else {
        for (i = 0; i < n; i++) {
            if (a[i] == 1) {
                p = i;
                break;
            }
        }
    }
    
    if (p == -1) {
        puts("0");
        return 0;
    } else if (p == 0) {
        for (i = 2; i <= n; i++) ans = ans * i % mod;
        printf("%lld\n", ans);
        return 0;
    }
    
    for (i = p; i < p + n; ) {
        if (f[a[i]] == 1) {
            puts("0");
            return 0;
        }
        
        f[a[i]] = 1;
        
        for (j = i; j < p + n; j++) {
            if (a[i] != a[j]) break;
        }
        
        if (a[i] == 1) {
            c = j - i;
        } else if (j - i > c) {
            puts("0");
            return 0;
        }
        
        v.push_back(make_pair(a[i], make_pair(i, j - i)));
        i = j;
    }
    
    sort(v.begin(), v.end());
    
    s.insert(make_pair(-1e9, -1e9));
    s.insert(make_pair(1e9, 1e9));
    
    for (i = 1, j = 0; i <= n; i++) {
        if (j == v.size() || v[j].first != i) {
            ans = ans * num % mod;
            num--;
        } else {
            int x = v[j].first;
            int y = v[j].second.first;
            int z = v[j].second.second;
            
            j++;
            
            if (a[y + z] > x) {
                if (a[y - 1] > x && z != c) {
                    puts("0");
                    return 0;
                }
            } else if (a[y - 1] < x) {
                ans = ans * (c - z + 1) % mod;
            }
            
            it = s.lower_bound(make_pair(y, 0));
            it2 = it;
            it2--;
            
            if (it2->second == y && it->first == y + z) {
                int l = it2->first;
                int r = it->second;
                
                num += z - 1 + c - 1;
                s.erase(it);
                s.erase(it2);
                s.insert(make_pair(l, r));
            } else if (it2->second == y) {
                int l = it2->first;
                int r = y + z;
                
                if (y + z == p + n) num += c - 1;
                
                num += z - 1;
                s.erase(it2);
                s.insert(make_pair(l, r));
            } else if (it->first == y + z) {
                int l = y;
                int r = it->second;
                
                num += z - 1;
                s.erase(it);
                s.insert(make_pair(l, r));
            } else {
                if (y + z == p + n) num += z - 1;
                
                s.insert(make_pair(y, y + z));
            }
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}