#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

const int MAXN = 3000001;

int A[MAXN];
int N;

bool done[MAXN];

pair<int, int> I[MAXN];

int Ilen(pair<int, int> p) {
	if (p.first >= p.second)
		return p.first - p.second + 1;
	return N - p.second + p.first + 1;
}

bool used[MAXN];


int main() {
	ios_base::sync_with_stdio(false);
	
	cin >> N;
	FOR (i, N) {
		cin >> A[i];
		A[i]--;
	}

	int idx = 0, val = A[0];
	while (idx < N && A[idx] == val)
		idx++;
	idx--;
	int last = idx;
	
	FOR (i, N)
		I[i].first = I[i].second = -1;
		
	SET(done, 0);
		
	while (true) {
		val = A[idx];
		if (done[val]) {
			cout << "0" << endl;
			return 0;
		}
		int j = idx;
		while (true) {
			j--;
			if (j < 0)
				j = N - 1;
			if (j == last || A[j] != val)
				break;
		}
		
		j = (j + 1) % N;
		
		I[val].first = idx;
		I[val].second = j;
		done[val] = true;
		idx = j - 1;
		if (idx < 0)
			idx = N - 1;
		if (idx == last)
			break;
	}
	
	int len0 = Ilen(I[0]);
	LL ret = 1LL;
	SET(used, 0);
	int numI = 0, marked = 0, taken = 0;
	
	FOR (i, N) {
		if (I[i].first == -1) {
//			cout << "entered" << endl;
//			cout << ret << " " << (marked - taken - (len0 - 1) * numI) << endl;
			ret *= (marked - taken - (len0 - 1) * numI);
//			cout << marked << " " << taken << " " << numI << " " << ret << endl;
			ret %= 998244353LL;
			taken++;
			continue;
		}

		int len = Ilen(I[i]);
		if (len > len0) {
			cout << "0" << endl;
			return 0;
		}
		
		int idx = I[i].first;
		used[idx] = true;
		while (idx != I[i].second) {
			idx--;
			if (idx < 0)
				idx = N - 1;
			used[idx] = true;
		}
		
		int before = (I[i].first + 1) % N;
		int after = I[i].second - 1;
		if (after < 0)
			after = N - 1;

		marked += len;
		taken++;
		if (!used[before] && !used[after]) {
			if (len < len0) {
				cout << "0" << endl;
				return 0;
			}
			numI++;
		}
		else {
			if (used[before] && used[after]) {
				ret *= (len0 - len + 1);
				ret %= 998244353LL;;
			}
		}
		
		if (marked == N)
			numI = 0;
	}
	
	cout << ret << endl;
	return 0;
}