#pragma once
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = (1 << 30) - 1;
const ll INF = (1ll << 62) - 1;
const int logo = 17;
const int MAXN = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct tour{
int seg[trsz];
void update(int x, int vl){
x += off;
seg[x] = vl;
for(x /= 2; x; x /= 2) seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
}
int query(int l, int r){
int ret = 0;
for(l += off, r += off; l < r; l >>= 1, r >>= 1){
if(l & 1) ret = max(ret, seg[l++]);
if(r & 1) ret = max(ret, seg[--r]);
}
return ret;
}
int spusti(int x, int vl, bool fl){
if(x >= off) return x - off;
int pr = x * 2;
if(fl) pr = x * 2 + 1;
if(seg[pr] >= vl) return spusti(pr, vl, fl);
return spusti(pr ^ 1, vl, fl);
}
int nadi(int l, int r, int vl, int fl){
vi lef, rig;
for(l += off, r += off; l < r; l >>= 1, r >>= 1){
if(l & 1) lef.PB(l++);
if(r & 1) rig.PB(--r);
}
while(rig.size()) lef.PB(rig.back()), rig.PPB();
int ans = 0;
if(fl == 0){
for(auto &x : lef){
if(ans == 0 and seg[x] >= vl) ans = spusti(x, vl, 0);
}
}else{
for(auto it = lef.rbegin(); it != lef.rend(); it++){
if(ans == 0 and seg[*it] >= vl) ans = spusti(*it, vl, 1);
}
}
return ans;
}
}t;
struct tdelta{
struct node{
int v1, v2, ret1, ret2;
node(){
v1 = inf, v2 = -inf, ret1 = 0, ret2 = 0;
}
};
node seg[trsz];
node merge(node a, node b){
node c;
c.v1 = min(a.v1, b.v1);
c.v2 = max(a.v2, b.v2);
c.ret1 = max(a.ret1, b.ret1);
c.ret1 = max(c.ret1, b.v2 - a.v1);
c.ret2 = max(a.ret2, b.ret2);
c.ret2 = max(c.ret2, a.v2 - b.v1);
return c;
}
void update(int x, int vl){
x += off;
seg[x].v1 = seg[x].v2 = vl;
for(x /= 2; x; x /= 2) seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
}
ii query(int l, int r){
if(l > r) return {0, 0};
node ret;
vi lef, rig;
for(l += off, r += off; l < r; l >>= 1, r >>= 1){
if(l & 1) lef.PB(l++);
if(r & 1) rig.PB(--r);
}
while(rig.size()) lef.PB(rig.back()), rig.PPB();
for(auto &x : lef) ret = merge(ret, seg[x]);
return {ret.ret1, ret.ret2};
}
int cm ;
int spusti(int x, int vl){
if(x >= off) return x - off;
if(seg[x * 2].ret1 >= vl or seg[x * 2].v2 - cm >= vl) return spusti(x * 2, vl);
cm = min(cm, seg[x * 2].v1);
return spusti(x * 2 + 1, vl);
}
int nadi(int l, int r, int vl){
vi lef, rig;
for(l += off, r += off; l < r; l >>= 1, r >>= 1){
if(l & 1) lef.PB(l++);
if(r & 1) rig.PB(--r);
}
while(rig.size()) lef.PB(rig.back()), rig.PPB();
cm = inf;
int ret = inf;
for(auto &x : lef){
if(seg[x].ret1 >= vl or seg[x].v2 - cm >= vl){
ret = spusti(x, vl);
return ret;
}
cm = min(cm, seg[x].v1);
}
return ret;
}
}del;
bool submit;
struct per{
struct node{
node *L, *R;
int cnt, mi, mx;
node(){
L = R = 0;
cnt = mi = mx = 0;
}
node(node *_L, node *_R, int _cnt, int _mi, int _mx){
L = _L, R = _R, cnt = _cnt, mi = _mi, mx = _mx;
}
};
typedef node* pnode;
pnode rt[MAXN];
set<pnode> st;
pnode l(pnode x){return x ? x -> L : 0;}
pnode r(pnode x){return x ? x -> R : 0;}
int c(pnode x){return x ? x -> cnt : 0;}
int sm(pnode x){return x ? x -> mi : 0;}
int bg(pnode x){return x ? x -> mx : 0;}
void update(pnode &x, int lo, int hi, int a, int b, int vl){
if(lo >= b or hi <= a) return;
if(!submit) st.insert(x);
x = new node(l(x), r(x), c(x), sm(x), bg(x));
if(!submit) st.insert(x);
if(lo >= a and hi <= b){
if(vl){
x -> cnt = 1;
x -> mi = lo;
x -> mx = lo;
}else{
x -> cnt = 0;
x -> mi = inf;
x -> mx = -inf;
}
return;
}
int mid = (lo + hi) / 2;
update(x -> L, lo, mid, a, b, vl);
update(x -> R, mid, hi, a, b, vl);
x -> mi = min(sm(x -> L), sm(x -> R));
x -> mx = max(bg(x -> L), bg(x -> R));
x -> cnt = c(x -> L) + c(x -> R);
}
int query(pnode &x, int lo, int hi, int a, int b){
if(lo >= b or hi <= a or !x) return 0;
if(lo >= a and hi <= b) return c(x);
int mid = (lo + hi) / 2;
return query(x -> L, lo, mid, a, b) + query(x -> R, mid, hi, a, b);
}
ii merge(ii a, ii b){
return {min(a.X, b.X), max(a.Y, b.Y)};
}
ii qry(pnode &x, int lo, int hi, int a, int b){
if(lo >= b or hi <= a or !x) return {inf, -inf};
if(lo >= a and hi <= b) return {sm(x), bg(x)};
int mid = (lo + hi) / 2;
return merge(qry(x -> L, lo, mid, a, b), qry(x -> R, mid, hi, a, b));
}
void update(int tim, int a, int b, int vl){
update(rt[tim], 0, off, a, b, vl);
}
void res(){
for(auto &x : st) delete x;
st.clear();
}
int query(int tim, int l, int r){
return query(rt[tim], 0, off, l, r);
}
ii query2(int tim, int l, int r){
return qry(rt[tim], 0, off, l, r);
}
}p;
int pm[MAXN], pv[MAXN], vl[MAXN], arr[MAXN];
vii st;
vi upd[MAXN], vals;
void init(int n, vi aa){
submit = 1;
for(int i=0; i<n; i++) arr[i + 1] = aa[i];
st.clear();
arr[0] = 2 * inf;
arr[n + 1] = 2 * inf;
t.update(0, 2 * inf);
t.update(n + 1, 2 * inf);
st.PB({-1, -inf});
for(int i=1; i<=n; i++){
while(st.back().Y > arr[i]) st.PPB();
pm[i] = st.back().X;
st.PB({i, arr[i]});
t.update(i, arr[i]);
del.update(i, arr[i]);
}
st.clear();
st.PB({n + 2, -inf});
for(int i=n; i; i--){
while(st.back().Y > arr[i]) st.PPB();
pv[i] = st.back().X;
st.PB({i, arr[i]});
}
for(int i=1; i<=n; i++){
int a = pm[i], b = pv[i];
int op = min(t.query(a + 1, i), t.query(i + 1, b));
op = max(op, arr[i]);
vl[i] = op - arr[i];
vals.PB(vl[i]);
}
vals.PB(0);
vals.PB(inf);
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for(int i=1; i<=n; i++){
vl[i] = lower_bound(all(vals), vl[i]) - vals.begin();
upd[vl[i] + 1].PB(i);
}
p.rt[0] = NULL;
for(int i=1; i<=n; i++) p.update(0, i, i + 1, 1);
for(int i=1; i<(int)vals.size(); i++){
p.rt[i] = p.rt[i - 1];
for(auto &x : upd[i]) p.update(i, x, x + 1, 0);
}
}
int max_towers(int l, int r, int d){
l++, r++;
auto it = lower_bound(all(vals), d) - vals.begin();
int lef, rig, sum = p.query(it, l, r + 1);
if(sum == 0){
if(r - l + 1 >= 3){
int najl = del.nadi(l, r + 1, d);
if(del.query(najl, r + 1).Y >= d) return 2;
}
return 1;
}
tie(lef, rig) = p.query2(it, l, r + 1);
int opt = t.nadi(l, lef, arr[lef] + d, 1);
if(opt) if(del.query(l, opt + 1).X >= d) sum++;
opt = t.nadi(rig + 1, r + 1, arr[rig] + d, 0);
if(opt) if(del.query(opt, r + 1).Y >= d) sum++;
return sum;
}
void zavrsi(){
p.res();
}
