#include <iostream>
#include <cassert>
#include <algorithm>
#include <set>
#include <string>
#define llint long long
#define mod 998244353

using namespace std;

llint n;
llint a[5005], b[5005];
set<string> S;

string s;
void dfs()
{
	if(S.count(s)) return;
	S.insert(s);
	for(int i = 1; i < s.size(); i++){
		if(s[i-1] == s[i]) continue;
		char x = s[i-1], y = s[i];
		s[i-1] = s[i] = min(x, y);
		dfs();
		s[i-1] = x, s[i] = y;
	}
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	assert(n >= 1 && n <= 5000);
	for(int i = 1; i <= n; i++) b[i] = a[i];
	sort(b+1, b+n+1);
	for(int i = 1; i <= n; i++) assert(b[i] == i);
	
	
	for(int i = 1; i <= n; i++) s += a[i]+'0';
	
	dfs();
	cout << S.size() << endl;
	
	return 0;
}