#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;
vector<ll> raw;
vector<int> a;
vector<vector<vector<int>>> v; // v[parity][dish_id] → list of “half‐positions”
vector<vector<map<int,int>>> cnt; // cnt[parity][dish_id][hei] → count
ll ans = 0;
int bua;
void solve(int id, int k) {
// “magic” offset so hei never goes negative
const int ma = 250005;
auto &vk = v[id][k];
int res = 0;
// initial hei = ma − first_halfpos + 1
int hehe = ma - vk[0] + 1;
int mi = hehe;
for (int i = 0; i + 1 < (int)vk.size(); i++) {
int pos = vk[i];
// map back to original index q in [1..n]
int q = (pos - id) * 2 + id;
// if the element at q equals this dish
if (a[q] == k) {
if (hehe <= ma) ans += cnt[id][k][hehe] + 1;
else ans += cnt[id][k][hehe];
}
// if two consecutive elements are equal, we “step up” hei
if (a[q] == a[q+1]) {
if (hehe <= ma) res += cnt[id][k][hehe] + 1;
else res += cnt[id][k][hehe];
hehe++;
}
// record current hei
cnt[id][k][hehe]++;
ans += res * 2;
if (q + 1 == n) ans -= res;
// now “slide” hei back down, one step per gap until the next vk[i+1]
int gap = vk[i+1] - vk[i] - 1;
int t = min(hehe - mi, gap);
bua = hehe - gap;
while (t--) {
hehe--;
if (hehe <= ma) res -= cnt[id][k][hehe] + 1;
else res -= cnt[id][k][hehe];
ans += res * 2;
// adjust final correction
if (n % 2 != id && hehe == bua && i == (int)vk.size() - 2)
ans -= res;
cnt[id][k][hehe]++;
}
// restore hei to bua for next iteration
hehe = bua;
mi = min(mi, hehe);
}
// handle the very last element if it sits at index n with this parity
if (n % 2 == id && a[n] == k) {
if (hehe <= ma) ans += cnt[id][k][hehe] + 1;
else ans += cnt[id][k][hehe];
}
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 1) Read
cin >> n;
raw.resize(n+1);
for (int i = 1; i <= n; i++) {
cin >> raw[i];
}
// 2) Compress dish‐values into [0..U-1]
vector<ll> comp(raw.begin()+1, raw.end());
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int U = comp.size();
a.assign(n+2, 0);
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(comp.begin(), comp.end(), raw[i]) - comp.begin();
}
// 3) Resize our per‐dish data structures
v .assign(2, vector<vector<int>>(U));
cnt .assign(2, vector<map<int,int>>(U));
// Build the lists of “half‐positions” for each (parity, dish)
for (int i = 1; i < n; i++) {
int id = i % 2;
int x = a[i];
int y = a[i+1];
v[id][x].pb(i/2 + id);
if (x != y) v[id][y].pb(i/2 + id);
}
// Append the virtual “end” marker for each dish
for (int x = 0; x < U; x++) {
v[1][x].pb(n/2 + 1);
v[0][x].pb((n+1)/2);
}
// 4) Run solve() for every parity & every dish
for (int id = 0; id < 2; id++) {
for (int x = 0; x < U; x++) {
solve(id, x);
}
}
// 5) Output the answer
cout << ans << "\n";
return 0;
}
