// Ý tưởng cơ bản: Duyệt qua tất cả các đoạn con (l, r)
// Với mỗi đoạn, đếm tần suất các phần tử.
// Nếu phần tử nào đó có tần suất > len/2 thì đoạn đó không tốt.
// Độ phức tạp O(N^2), không khả thi với N=500,000.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i) cin >> a[i];

    long long ans = 0;
    for(int l=0; l<n; ++l) {
        map<int, int> cnt;
        int max_freq = 0;
        for(int r=l; r<n; ++r) {
            cnt[a[r]]++;
            max_freq = max(max_freq, cnt[a[r]]);
            int len = r - l + 1;
            // Điều kiện 'tốt': mọi phần tử <= len/2
            // Tương đương với phần tử nhiều nhất <= len/2
            if(max_freq * 2 <= len) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

// Ý tưởng dựa trên giải pháp của hanalala
// 1. Chỉ các phần tử có tần suất cao mới có thể vi phạm điều kiện (xuất hiện > len/2).
// 2. Nếu một phần tử có tổng tần suất t < N/2, nó không bao giờ có thể là majority ở bất kỳ đoạn nào.
// 3. Chỉ cần xét các phần tử có tần suất >= N/2 (số lượng ít, <= 2).
// 4. Với mỗi phần tử ứng cử viên, dùng segment tree/lazy propagation để đếm số đoạn mà nó là majority.
// 5. Các đoạn không tốt là các đoạn có majority. Tổng số đoạn tốt = Tổng số đoạn - Số đoạn không tốt.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 500005;
int n, a[MAXN];
vector<int> pos[MAXN];

// Segment Tree để xử lý các bài toán về prefix sum và FWT/DP
// Cấu trúc node lưu tổng sum và lazy propagation
struct Node {
    ll sum, lazy;
} tree[4 * MAXN];

void down(int id, int l, int r) {
    if (tree[id].lazy) {
        int mid = (l + r) >> 1;
        tree[id<<1].lazy += tree[id].lazy;
        tree[id<<1].sum += tree[id].lazy * (mid - l + 1);
        tree[id<<1|1].lazy += tree[id].lazy;
        tree[id<<1|1].sum += tree[id].lazy * (r - mid);
        tree[id].lazy = 0;
    }
}

void update(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        tree[id].lazy += val;
        tree[id].sum += 1LL * val * (r - l + 1);
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    update(id<<1, l, mid, u, v, val);
    update(id<<1|1, mid+1, r, u, v, val);
    tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
}

ll query(int id, int l, int r, int u, int v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[id].sum;
    down(id, l, r);
    int mid = (l + r) >> 1;
    return query(id<<1, l, mid, u, v) + query(id<<1|1, mid+1, r, u, v);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }

    ll total = 1LL * n * (n + 1) / 2;
    ll bad = 0;

    // Chỉ xét các phần tử có số lượng >= N/2
    // Nếu t < N/2, đoạn con mà nó là majority không t tồn tại.
    for (int x = 1; x <= 500000; ++x) {
        if (pos[x].empty()) continue;
        int cnt = pos[x].size();
        if (cnt * 2 < n) continue;

        // Reset樹
        memset(tree, 0, sizeof(tree));

        // Duyệt qua các đoạn mà x có thể là majority
        // Xử lý logic đếm số đoạn (l, r) sao cho số lần x xuất hiện > (r-l+1)/2
        // Tức là 2 * freq > len => 2 * (pre_x - pre_x_start) > (r - l + 1)
        // Biến đổi: 2 * pre_x - r > 2 * pre_x_start - l + 1
        // Dùng segment tree lưu giá trị (2*index - pos[index]) để tìm số lượng l thỏa mãn

        // Code chi tiết khá phức tạp, tóm tắt ý tưởng:
        // Duyệt r từ 1 đến n. Với mỗi r, cập nhật các vị trí l có thể.
        // Sử dụng lazy segtree để range update và range query.
        // Ví dụ: với mỗi vị trí i, ta cần update range để tính toán.
        // Giải pháp gốc dùng FWT hoặc logic tương tự.
        // Ở đây ta minh họa logic chính:
        // Duyệt qua các đoạn giữa các vị trí của x.

        // Code mẫu minh họa logic (giản lược):
        // Giả sử ta dùng vector pos[x] = {p1, p2, ..., pk}
        // Ta cần đếm số cặp (l, r) sao cho số lần x xuất hiện > (r-l+1)/2
        // Tức là (2 * cnt_x) > (r - l + 1)
        // (2 * cnt_x) + l > r

        // Đoạn code đầy đủ thường dùng 2 con trỏ hoặc segment tree.
        // Ví dụ: Duyệt r, duy trì con trỏ l sao cho số lượng x > (r-l+1)/2.
        // Nếu tại r, số lượng x là k, thì l phải nhỏ hơn r - 2*k + 1.
        // Tuy nhiên, cần loại trừ các đoạn mà x KHÔNG phải là majority duy nhất.
        // Giải pháp thường dùng FWT hoặc offline query.
    }

    cout << total - bad << endl;
    return 0;
}

// Ý tưởng từ giải pháp 111_LeQuangTam
// Thay vì đếm các đoạn không tốt, ta trực tiếp đếm các đoạn tốt.
// Một đoạn con tốt thỏa mãn: max_freq <= len/2.
// Điều này tương đương với: với mọi phần tử x, 2 * count(x) <= len.
// Hoặc: 2 * count(x) - len <= 0.
// Xét prefix sum của mỗi giá trị.
// QHĐ: dp[r] = số lượng l sao cho đoạn [l, r] tốt.
// Hoặc dùng 2 con trỏ.
// 
// Có một liên kết thú vị: Nếu đoạn [l, r] tốt, thì nó KHÔNG chứa majority element.
// Ta có thể dùng kỹ thuật 'Mo's algorithm' hoặc 'Segment tree beats' nhưng N=500k.
// 
// Giải pháp tối ưu thường là:
// 1. Nếu đoạn dài, majority element phải có tần suất cao. Chỉ cần kiểm tra các phần tử xuất hiện nhiều nhất.
// 2. Nếu đoạn ngắn, có thể dùng brute force.
// 
// Code dưới đây là cách tiếp cận 'Fix the majority':
// Chỉ có tối đa 2 phần tử có thể là majority cho toàn mảng (nếu t >= N/2).
// Các phần tử khác không thể tạo ra đoạn không tốt quá dài.
// Tuy nhiên, ta cần đếm đoạn tốt.
// 
// Một cách tiếp cận khác (được đề cập trong các giải pháp):
// Sử dụng Segment Tree với Lazy Propagation để xử lý các mảng cộng dồn.
// Xét điều kiện: 2 * freq(x, l, r) - (r-l+1) <= 0.
// Hoặc: 2 * (pref_x[r] - pref_x[l-1]) - (r - l + 1) <= 0
// => 2 * pref_x[r] - r <= 2 * pref_x[l-1] - (l-1) - 1
// 
// Để đếm các đoạn tốt, ta cần thỏa mãn điều kiện với TẤT CẢ các x.
// Rất khó để xử lý đồng thời.
// 
// Thay vào đó, ta dùng kỹ thuật 'Two Pointers' với điều kiện:
// Với mỗi l, tìm r_max sao cho đoạn [l, r] vẫn tốt.
// Nếu ta có thể duy trì tần suất các phần tử trong đoạn [l, r] một cách hiệu quả.
// 
// Code minh họa ý tưởng Two Pointers:
// Duyệt l từ 1 đến n. Duy trì r sao cho đoạn [l, r] tốt.
// Khi l tăng, loại a[l-1] khỏi đoạn.
// Khi r tăng, thêm a[r] vào đoạn.
// Cần kiểm tra điều kiện max_freq <= len/2.
// Theo dõi max_freq hiệu quả? Khó.
// 
// Thay vào đó, dùng giải pháp 'Counting bad segments' và trừ.
// Hoặc dùng giải pháp từ code mẫu:
// Dùng Segment Tree để lưu các giá trị 2*pref[x] - index.
// Với mỗi r, ta cần đếm số l sao cho đoạn [l, r] tốt.
// Điều này có nghĩa là với mọi x, 2*(pref_x[r] - pref_x[l-1]) <= r - l + 1.
// => 2*pref_x[r] - r <= 2*pref_x[l-1] - l + 1.
// Vì có nhiều x, ta cần tìm max của (2*pref_x[r] - r) và so sánh.
// Ta chỉ cần quan tâm đến phần tử xuất hiện nhiều nhất trong đoạn [l, r].
// 
// Code giải pháp (gợi ý):
// Duyệt r từ 1..n.
// Duy trì một cấu trúc dữ liệu để lấy phần tử có tần suất lớn nhất trong đoạn [l, r] đang xét.
// Hoặc đơn giản hơn, dùng giải pháp 'Fix Majority Candidate'.
// Chỉ có 2 ứng cử viên cho majority toàn cục.
// Với các đoạn khác, majority phải là 1 trong 2 ứng cử viên này.
// Nếu đoạn không chứa majority toàn cục, nó automatically tốt? Không, vì majority cục bộ có thể là phần tử khác.
// 
// Tuy nhiên, có một quan sát quan trọng:
// Nếu một đoạn không tốt, nó phải có phần tử xuất hiện > len/2.
// Nếu ta xét t tổng số đoạn, và trừ đi các đoạn không tốt.
// Các đoạn không tốt là các đoạn chứa majority.
// Majority có thể là bất kỳ phần tử nào.
// Nhưng chỉ các phần tử có tần suất cao mới có thể tạo ra đoạn không tốt đủ dài.
// 
// Code hoàn chỉnh dựa trên bài giải:
// Duyệt qua các phần tử 'nóng' (tần suất >= N/2).
// Với mỗi phần tử nóng, đếm số đoạn mà nó là majority.
// Để ý, nếu một đoạn có majority, majority đó phải là phần tử có tần suất cao nhất trong đoạn.
// Nếu ta trừ đi các đoạn có majority là các phần tử nóng.
// Liệu có đoạn không tốt mà majority là phần tử tần suất thấp? Có.
// Ví dụ: [1, 1, 2] majority là 1 (tần suất cao). [2, 2, 3] majority là 2 (tần suất cao).
// Nếu t tổng tần suất của 1 và 2 đều thấp, làm sao đoạn [1, 1, 2] không tốt?
// Nếu [1, 1, 2] không tốt, 2*2 > 3 => sai.
// Nếu [2, 2, 3] không tốt, 2*2 > 3 => sai.
// 
// Quan sát: Nếu một đoạn [l, r] không tốt, nó có majority m.
// Nếu freq(m) > (r-l+1)/2, thì freq(m) > (r-l+1)/2 >= (Tổng tần suất của các phần tử khác).
// Vậy m chiếm hơn một nửa.
// Nếu t tổng tần suất của m trong toàn mảng < N/2, thì làm sao m có thể chiếm > một nửa trong [l, r]?
// Câu trả lời là: [l, r] phải ngắn. Rất ngắn.
// Ví dụ: freq(m) = 5, N = 100. m có thể là majority trong đoạn [l, r] độ dài 9 (5 > 4.5).
// Nhưng nếu freq(m) < N/2, các đoạn không tốt mà m là majority sẽ bị giới hạn độ dài.
// 
// Thực tế, giải pháp accepted dùng FWT hoặc Segment Tree để đếm số đoạn không tốt.
// Hoặc dùng kỹ thuật 'divide and conquer'.
// 
// Dưới đây là code minh họa cách đếm số đoạn không tốt bằng cách duyệt qua các ứng cử viên.
//