NEXUS

// https://drive.google.com/file/d/1UddFXyAgbKzDbvuurMHOZauboXSr2i3c/view?usp=sharing
#define task "NEXUS"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr int Inf = 1e9 + 7;
int n, d, a[N];

void Read()
{
    cin >> n >> d;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

/*Subtask 1*/

void Sub_1()
{
    int ans(0);

    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
        {
            for (int t = j, sum(0); t >= i; sum += a[t--] > 0)
                if (a[t] > t - i || sum + a[t] > d)
                    goto done;

            ++ans;
        done:;
        }

    cout << ans;
}

/*End Subtask 1*/

/*Subtask 2*/

bool Check(int i, int j)
{
    for (int t = j, sum(0); t >= i; sum += (a[t--] > 0))
        if (sum + a[t] > d)
            return false;
    return true;
}

void Sub_2()
{
    int ans(0);

    for (int i = 1; i <= n; ++i)
    {
        int l = 1, m, h = i;
        while (l <= h)
        {
            m = (l + h) / 2;
            if (Check(m, i))
                h = m - 1;
            else
                l = m + 1;
        }

        for (int j = i, minn = Inf; j >= l; --j)
        {
            minn = min(minn, j - a[j]);
            if (j <= minn)
                ++ans;
        }
    }

    cout << ans;
}

/* End Subtask 2*/

/*Subtask 4*/

vector<pair<int, int>> pos;

ll DAC(int left, int right)
{
    if (left > right)
        return 0;

    int mid = (left + right) / 2;
    ll ans(0);

    {
        pos.clear();
        int l = mid, m, h = right;

        while (l <= h)
        {
            m = (l + h) / 2;
            if (Check(mid, m))
                l = m + 1;
            else
                h = m - 1;
        }

        for (int i = mid, minn = Inf, cnt(-(a[mid] > 0)); i <= h; ++i)
        {
            minn = min(minn, i - a[i]);
            cnt += a[i] > 0;
            pos.emplace_back(minn, cnt);
        }
    }

    {
        for (int i = mid, j = 0, minn = Inf, cnt = 0, minid = Inf; i >= left; --i)
        {
            while (j < (int)pos.size() && pos[j].first >= i)
                ++j;

            minid = min(minid, i - a[i]);
            minn = min(minn, d - cnt - a[i]);

            if (minid >= i)
            {
                int l = 0, m, h = j - 1;
                while (l <= h)
                {
                    m = (l + h) / 2;
                    if (pos[m].second <= minn)
                        l = m + 1;
                    else
                        h = m - 1;
                }
                ans += l;
                // cerr << left << " " << right << " --- " << mid << ": " << i << " " << f.Get(Find(sx, minn + 1) - 1) << "\n";
            }

            cnt += a[i] > 0;
        }
    }

    ans += DAC(left, mid - 1);
    ans += DAC(mid + 1, right);

    return ans;
}

void Sub_4()
{
    cout << DAC(1, n);
}

/*End Subtask 4*/

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    if (n <= 200)
        Sub_1();
    else if (n <= 2000)
        Sub_2();
    else
        Sub_4();
}