#include <bits/stdc++.h>
using namespace std;
int N, K;
struct SegTree {
const int INF = 1e9;
struct Node {
int mn, cnt;
int lazy;
};
vector <Node> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 1);
}
inline void solve_lazy(int nod) {
if(2 * nod + 1 <= 4 * n) {
aint[2 * nod].lazy += aint[nod].lazy;
aint[2 * nod + 1].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
inline void refresh(int nod) {
aint[nod].cnt = aint[2 * nod].cnt + aint[2 * nod + 1].cnt;
aint[nod].mn = min(aint[2 * nod].mn + aint[2 * nod].lazy, aint[2 * nod + 1].mn + aint[2 * nod + 1].lazy);
}
void build(int nod, int left, int right, int *D) {
if(left == right) {
aint[nod].mn = K - D[left - 1];
if(aint[nod].mn <= 0) {
aint[nod] = {INF, 1, 0};
}
}
else {
int mid = (left + right) / 2;
build(2 * nod, left, mid, D);
build(2 * nod + 1, mid + 1, right, D);
refresh(nod);
}
}
void update(int nod, int left, int right, int l, int r) {
if(l <= left && right <= r && aint[nod].mn + aint[nod].lazy - 1 > 0) {
aint[nod].lazy--;
return ;
}
if(left == right) {
aint[nod] = {INF, 1, 0};
return ;
}
solve_lazy(nod);
int mid = (left + right) / 2;
if(l <= mid) update(2 * nod, left, mid, l, r);
if(mid < r) update(2 * nod + 1, mid + 1, right, l, r);
refresh(nod);
}
int query(int nod, int left, int right, int l, int r) {
if(l <= left && right <= r) {
return aint[nod].cnt;
}
else {
int mid = (left + right) / 2;
int ans = 0;
if(l <= mid) ans += query(2 * nod, left, mid, l, r);
if(mid < r) ans += query(2 * nod + 1, mid + 1, right, l, r);
return ans;
}
}
}st;
void inicjuj(int n, int k, int *D) {
N = n, K = k;
st.init(N);
st.build(1, 1, N, D);
}
void podlej(int a, int b) {
a++, b++;
st.update(1, 1, N, a, b);
}
int dojrzale(int a, int b) {
a++, b++;
return st.query(1, 1, N, a, b);
}
