#include "towers.h"
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
#define SN 300000
#define inf 2e9
using namespace std;
struct points
{
	int x,y;
	bool operator == (const points &t)const
	{
		return x==t.x&&y==t.y;	
	}
	bool operator < (const points &t)const
	{
		if (x!=t.x) return x<t.x;
		return y<t.y;
	}
};
struct reads
{
	int l,r,d,op;
	bool operator < (const reads &t)const
	{
		return d<t.d;	
	}
};
reads tong[SN+1];
int n,length,q[SN+1],rt[SN+1],h[SN+1],dque[SN+1],top,depth[SN+1],ls[SN+1],rs[SN+1],fa[SN+1][21];
set<int>s;
void dfs(int x)
{
	if (ls[x]) fa[ls[x]][0]=x,depth[ls[x]]=depth[x]+1,dfs(ls[x]);
	if (rs[x]) fa[rs[x]][0]=x,depth[rs[x]]=depth[x]+1,dfs(rs[x]);
	return;
}
int lca(int x,int y)
{
	if (depth[x]<depth[y]) swap(x,y);
	for (int i=log(n)/log(2);i>=0;--i)
		if (depth[fa[x][i]]>=depth[y])
			x=fa[x][i];
	if (x==y) return x;
	for (int i=log(n)/log(2);i>=0;--i)
		if (fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
bool cmp(int x,int y)
{
	return h[x]<h[y];
}
bool cmp2(points a,points b)
{
	return a.y<b.y;
}
struct KDT
{
	struct node
	{
		int x1,x2,y1,y2,op,ls,rs,data;
	};
	node tree[40*SN+1];
	int length;
	int build(int x1,int x2,int y1,int y2,int op,vector<points>p)
	{
		if (p.empty()) return 0;
		int nw=++length,mid;
		tree[nw]=(node){x1,x2,y1,y2,op,0,0,0};
		if (x1==x2&&y1==y2) return nw;
		vector<points>A;
		vector<points>B;
		if (!op)
		{
			mid=(x1+x2)>>1;
			for (int i=0;i<p.size();++i)
			{
				if (p[i].x<=mid) A.push_back(p[i]);
				else B.push_back(p[i]);
			}
			tree[nw].ls=build(x1,mid,y1,y2,!op,A),tree[nw].rs=build(mid+1,x2,y1,y2,!op,B);
		}
		else
		{
			mid=(y1+y2)>>1;
			for (int i=0;i<p.size();++i)
			{
				if (p[i].y<=mid) A.push_back(p[i]);
				else B.push_back(p[i]);
			}
			tree[nw].ls=build(x1,x2,y1,mid,!op,A),tree[nw].rs=build(x1,x2,mid+1,y2,!op,B);
		}
		return nw;
	}
	void push_up(int k)
	{
		tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data;
		return;
	}
	int add(int k,int x,int y,int d)
	{
		int nw=++length;
		tree[nw]=tree[k];
		if (tree[nw].x1==tree[nw].x2&&tree[nw].y1==tree[nw].y2)
		{
			tree[nw].data+=d;
			return nw;
		}
		if (!tree[nw].op)
		{
			if (x<=tree[tree[nw].ls].x2) tree[nw].ls=add(tree[nw].ls,x,y,d);
			else tree[nw].rs=add(tree[nw].rs,x,y,d);
		}
		else
		{
			if (y<=tree[tree[nw].ls].y2) tree[nw].ls=add(tree[nw].ls,x,y,d);
			else tree[nw].rs=add(tree[nw].rs,x,y,d);
		}
		push_up(nw);
		return nw;
	}
	int query(int k,int x,int y)
	{
		if (!k) return 0;
		if (tree[k].x2==x&&tree[k].y2==y) return tree[k].data;
		if (!tree[k].op)
		{
			if (x<=tree[tree[k].ls].x2) return query(tree[k].ls,x,y);
			else return query(tree[k].ls,tree[tree[k].ls].x2,y)+query(tree[k].rs,x,y);
		}
		else
		{
			if (y<=tree[tree[k].ls].y2) return query(tree[k].ls,x,y);
			else return query(tree[k].ls,x,tree[tree[k].ls].y2)+query(tree[k].rs,x,y);
		}
	}
};
KDT T;
void init(int N, std::vector<int> H)
{
	vector<points>p;
	int pv,nt,a,b;
	n=N;
	for (int i=1;i<=n;++i) q[i]=i,h[i]=H[i-1];
	for (int i=1;i<=n;++i)
	{
	    while (top&&h[dque[top]]<h[i]) ls[i]=dque[top],top--;
		if (top) rs[dque[top]]=i;
		dque[++top]=i;
	}
	depth[dque[1]]=1,dfs(dque[1]);
	for (int i=1;i<=log(n)/log(2);++i)
		for (int j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	sort(q+1,q+n+1,cmp);
	for (int i=1;i<=n;++i)
	{
		pv=nt=-1;
		auto it=s.lower_bound(q[i]);
		if (it!=s.end()) nt=(*it);
		if (it!=s.begin()) it--,pv=(*it);
		s.insert(q[i]),a=((pv==-1)?inf:h[lca(pv,q[i])]-h[q[i]]),b=((nt==-1)?inf:h[lca(nt,q[i])]-h[q[i]]);
		if (pv!=-1) tong[++length]=(reads){pv,q[i],a+1,-1};
		if (nt!=-1) tong[++length]=(reads){q[i],nt,b+1,-1};
		if (pv!=-1&&nt!=-1) tong[++length]=(reads){pv,nt,max(a,b)+1,1};
	}
	for (int i=1;i<=length;++i) p.push_back((points){n-tong[i].l+1,tong[i].r});
	rt[0]=T.build(1,n,1,n,0,p),sort(tong+1,tong+length+1);
	for (int i=1;i<=length;++i) rt[i]=T.add(rt[i-1],n-tong[i].l+1,tong[i].r,tong[i].op);
	return;
}
int max_towers(int L, int R, int D)
{
	L++,R++;
	int ps=lower_bound(tong+1,tong+length+1,(reads){0,0,D+1,0})-tong-1;
	return R-L+1+T.query(rt[ps],n-L+1,R);
}