#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e5 + 10;
int n, type, len, ans;
int a[N], bar[N], sum[N], vis[N];
struct BIT{
    int t[2 * N];
    int lowbit(int x){return x & (-x);}
    void add(int x, int val){
        x += n + 1;
        for(int i = x; i <= 2 * n + 1; i += lowbit(i))
            t[i] += val;
        return;
    }
    int sum(int x){
        x += n + 1;
        int res = 0;
        for(int i = x; i; i -= lowbit(i))
            res += t[i];
        return res;
    }
}T;
void solve1(int x){
    for(int i = 0; i <= 2 * n + 1; i++) sum[i] = T.t[i] = 0;
    T.add(0, 1);
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i - 1] + (a[i] == x ? 1 : -1);
        ans += T.sum(sum[i] - 1);
        T.add(sum[i], 1);
    }
}
void solve2(){
    for(int i = 0; i < n; i++) sum[i] = 0;
    for(int i = 1; i <= n; i++){
        int maxn = 0;
        for(int j = i; j <= min(i + 2 * len - 1, n); j++){
            sum[a[j]] += vis[a[j]];
            maxn = max(sum[a[j]], maxn);
            if(2 * maxn > j - i + 1) ans++;
        }
        for(int j = i; j <= min(i + 2 * len - 1, n); j++)
            sum[a[j]] -= vis[a[j]];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> type;
    len = sqrt(n);
    for(int i = 1; i <= n; i++) cin >> a[i], bar[a[i]]++;
    for(int i = 0; i < n; i++){
        if(bar[i] >= len) solve1(i);
        else vis[i] = 1;
    }
    solve2();
    out << ans << endl;
    return 0;
}