// ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
// ➡ @roadfromroi ⬅
// ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "queue"
//#include "towers.h"
#define all(x) x.begin(), x.end()
using namespace std;
vector<int> h;
int dd;
struct node {
int lval;
int rval;
int cnt;
int lstenka;
int rstenka;
node() {}
node(int x) {
lval = rval = x;
cnt = 1;
lstenka = 0;
rstenka = 0;
}
};
void merge(node &a, node b) {
if (a.rval <= b.lval) {
if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
a.cnt = a.cnt + b.cnt;
a.rstenka = b.rstenka;
a.rval = b.rval;
return;
} else {
a.cnt = a.cnt + b.cnt - 1;
if (b.cnt != 1) {
a.rstenka = b.rstenka;
a.rval = b.rval;
} else {
// cout << c.rstenka << ' ';
a.rstenka = max(a.rstenka, max(b.rstenka, max(b.lstenka, b.rval)));
// cout << c.rstenka << '\n';
}
return;
}
} else {
if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
b.cnt = a.cnt + b.cnt;
b.lstenka = a.lstenka;
b.lval = a.lval;
swap(a, b);
return;
} else {
b.cnt = a.cnt + b.cnt - 1;
if (a.cnt != 1) {
b.lstenka = a.lstenka;
b.lval = a.lval;
} else {
// cout << c.rstenka << ' ';
b.lstenka = max(b.lstenka, max(a.lstenka, max(a.rstenka, a.lval)));
// cout << c.rstenka << '\n';
}
swap(a, b);
return;
}
}
}
struct kornihunka{
vector<int> elems;
node nd;
void push(int x) {
elems.push_back(x);
}
node get(int l, int r) {
r = min(r, (int)elems.size() - 1);
node nres(elems[l]);
for (int i = l + 1; i <= r; ++i) {
merge(nres, node(elems[i]));
}
return nres;
}
int calc() {
int incdd = -1;
nd = node(elems[0]);
int cc = 1;
int pr3 = 2e9;
for (int i = 1; i < elems.size(); ++i) {
int pr = nd.rval, pr2 = nd.rstenka;
merge(nd, elems[i]);
if (nd.cnt != cc) {
cc = nd.cnt;
if (incdd == -1)
incdd = min(pr2 - dd - pr, pr3 - dd - pr);
incdd = min(incdd, min(pr2 - dd - pr, pr3 - dd - pr));
pr3 = pr2;
}
}
incdd = min(incdd, pr3 - dd - nd.rval);
if (nd.cnt == 1)
return 0;
return incdd + 1;
}
node getnode() {
return nd;
}
};
const int K = 330;
const int N = 100000;
vector<vector<kornihunka>> vecnode;
vector<vector<int>> detki;
int realdetki[N / K + 1][N];
vector<int> alex;
int calcedd = 0;
void init(int n, vector<int> hh) {
h = hh;
vecnode.assign((n + K - 1) / K, vector<kornihunka>(K));
detki.assign((n + K - 1) / K, {});
for (int i = 0; i < n; ++i) {
vecnode[i/K][0].push(h[i]);
}
for (int i = 0; i < vecnode.size(); ++i) {
int j = 0;
int inc = 1;
dd = 0;
do {
dd += inc;
detki[i].push_back(dd);
alex.push_back(dd);
vecnode[i][j + 1] = vecnode[i][j];
inc = vecnode[i][j].calc();
j++;
} while (inc != 0);
}
sort(all(alex));
alex.erase(unique(all(alex)), alex.end());
for (int i = 0; i < vecnode.size(); ++i) {
int j = 0;
for (int pvl = 0; pvl < alex.size(); ++pvl) {
while (j + 1 != detki[i].size() and detki[i][j + 1] <= alex[pvl]) {
j++;
}
realdetki[i][pvl] = j;
}
}
}
int max_towers(int L, int R, int D) {
node res(2e9);
dd = D;
int dvl = upper_bound(all(alex), dd) - alex.begin()-1;
if (L / K == R / K) {
//cout << upper_bound(all(detki[L/K]), dd) - detki[L/K].begin()-1 << '\n';
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, R % K));
return res.cnt;
}
if (L % K != 0) {
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, K - 1));
L = L / K * K + K;
}
while (L + K <= R + 1) {
//cout << "TT " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
node res2 = vecnode[L/K][0].getnode();
//cout << "TT2 " << res2.lval << ' ' << res2.lstenka << ' ' << res2.cnt << '\n';
merge(res, vecnode[L/K][realdetki[L/K][dvl]].getnode());
//cout << "TT3 " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
L += K;
}
if (L <= R) {
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, R % K));
}
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
return res.cnt;
}
/*
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
init(n, a);
for (int i = 0; i < m; ++i) {
int q1, q2, q3;
cin >> q1 >> q2 >> q3;
cout << max_towers(q1,q2,q3) << '\n';
}
}*/
/*
7 1
10 20 60 40 50 30 70
0 6 17
*/
