#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 500010, inf = maxn;
int n, a[maxn], _c[maxn], nxt[maxn], rb[maxn], rg[maxn], k;
ll res;
struct sgt {
    int v[maxn<<1];
    void init(){ fill(v, v+(maxn<<1), n); };
    void modify(int i, int pos) {
        for (i += n;i;i >>= 1)
            v[i] = min(v[i], pos);
    }
    int query(int l, int r) {
        int res = n;
        for (l += n, r += n;l < r;l >>= 1, r >>= 1) {
            if (l&1) res = min(res, v[l++]);
            if (r&1) res = min(res, v[--r]);
        }
        return res;
    }
    void reset(){ fill(v, v+(maxn<<1), 0); };
    void add(int i) { for (++i;i <= n;i += i & -i) ++v[i]; }
    int query(int k) {
        int res = 0;
        for (int i = 19;i >= 0;--i) {
            if (((1<<i) | res) <= n && v[(1<<i) | res] < k)
                k -= v[res |= 1<<i];
        }
        return res-1;
    }
    int qsum(int i) {
        int res = 0;
        for (++i;i;i ^= i & -i) res += v[i];
        return res;
    }
}vtree;
void make_nxt_small() {
    static vector<int> query[maxn];
    vtree.init();
    for (int i = 0;i < n;++i)
        query[ nxt[i] ].pb(i);
    for (int i = n;i >= 0;--i) {
        for (int u : query[i])
            rb[u] = vtree.query(0, a[u]);
        vtree.modify(a[i], i);
    }
}
void get_ans() {
    static bool cnt[maxn];
    vtree.reset();
    vector<int> v(n);
    for (int i = n-1;i >= 0;--i) {
        if (nxt[i] != i+1 && !cnt[nxt[i]]) vtree.add(nxt[i]), cnt[nxt[i]] = true;//, cout << "add " << nxt[i] << '\n';
        if (vtree.qsum(rg[i])+1 < k) continue;
        v[i] = min(rg[i]+1, vtree.query(k)) - max(i-1, vtree.query(k-1));

        res += min(rg[i]+1, vtree.query(k)) - max(i-1, vtree.query(k-1));
    }
//  cout << "V\n";
//  for (int i = 0;i < n;++i)
//      cout << v[i] << " \n"[i==n-1];
//  cout << '\n';
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 0;i < n;++i)
        cin >> a[i];
    vtree.init();
    iota(_c, _c+n, 0);
    sort(_c, _c+n, [&](int x, int y) { return a[x] < a[y]; });
    for (int i = 0;i < n;++i)
        a[ _c[i] ] = i;
    for (int i = n-1;i >= 0;--i) {
        nxt[i] = vtree.query(a[i]+1, n);
        vtree.modify(a[i], i);
    }
    make_nxt_small();
    rg[n] = n;
    for (int i = n-1;i >= 0;--i) {
        if (rg[i+1] < nxt[i]-1) rg[i] = rg[i+1];
        else rg[i] = min(rb[i]-1, rg[ nxt[i] ]);
    }
    get_ans();
    cout << res << '\n';
}