感觉还是挺有思维难度的一道题。蒟蒻想了不短时间才从暴力$O(n^3)$优化到$O(nlogn)$
纯暴力
$O(n^3)$ 暴力枚举区间内的点对，暴力扫描区间最大值。
稍微好点的暴力
最大值可以用线段树维护，优化到 $O(n^2logn)$。
（其实$st$表能达到 $O(n^2)$ ，不过蒟蒻早忘了咋写了。。。总之最大值可以用数据结构优化)
（重点！）高端的优化
似乎到上面就不是很好想了。瓶颈就在于枚举点对的 $n^2$。可不可以少枚举点东西？
一个点对 $(i,j)$ 的贡献与三个值有关：$a[i],a[j],max(a[k])(i<k<j)$
不枚举$i,j$，那就枚举中间的 $a[k]$。这里引入两个值：定义 $ll[i]$ 为从点 $i$ 向左走，直到遇到第一个大于它的数的位置（没有则为0）；同理，$rr[i]$就是向右走（没有则为n+1)。
也就是说，点 $i$ 是区间$[ll[i]+1,rr[i]-1]$的最大值，且满足这个区间长度最小。
这样，枚举这个点（记为 $i$ )的时候：（区间记为$[L,R]$）
- 如果 $ll[i]$ 与 $rr[i]$ 都在区间中，就会有一点对 $(ll[i],rr[i])$满足条件 $1$。
- 如果 $ll[i]$ 在区间中，那么每个点对 $(ll[i],k)(i<k<min(rr[i],R))$ 满足条件 $2$。（因为 $a[k]<a[i]$ ，$a[i]<a[ll[i]]$ ， $a[i]$ 为区间 $[ll[i]+1,k-1]$的最大值。注意不能走出去所以取min）
- 如果 $rr[i]$ 在区间中，那么每个点对 $(k,rr[i])(max(ll[i],L)<k<i)$ 满足条件 $2$。（原因同上）
这样就能得到 $O(n^2)$ 的做法。
顶级的优化
前面铺垫这么多，终于轮到正解出场了！
根据上面，我们需要一种方法，能快速得知：
- 每个 $ll[i]$ 在区间内的数的 $min(rr[i],R)-i$
- 每个 $rr[i]$ 在区间内的数的 $i-max(ll[i],L)$
- $ll[i]$，$rr[i]$都在区间内数的个数。
虽然有点麻烦，不过本题只有询问，是不是可以离线下来搞一搞呢？
先处理第一种。从右往左扫描数列，遇到某个数的 $ll[i]$ 再把这个数产生的贡献用某种数据结构维护起来，遇到某个询问的左端点就直接查询，这样保证了只有 $ll[i]$ 在区间内的数才会产生贡献。
具体来说：用线段树维护。遇到 $ll[i]$ 就把 $[i+1,rr[i]-1]$（注意不能取两端）加 $1$，遇到询问左端点就查询 $[L,R]$ 的和。仔细想想就会发现，这样也会在查询时相当于取了$min(rr[i],R)$。
第二种倒过来扫就好了。
第三种正着扫倒着扫皆可。以倒着扫为例：遇到 $ll[i]$ 把$[rr[i],n]$加 $1$（意为询问右端点落在$[rr[i],n]$都会覆盖到$rr[i]$，就有 1 贡献），这样查询时单点查 $R$ 即可。
时间复杂度：$O(nlogn)$（常数有点大最慢$1100ms+$。。。）
细节：1.关于预处理$ll$、$rr$：蒟蒻好像想复杂了，没有什么好方法，只能记录下位置，按权值排序后造棵平衡树倒着扫数列，插入每个点的位置，$ll$、$rr$分别查前驱后继。。。
2.统计的答案要开long long！
$update:$
3.有一点忘了说了：对于情况1，满足$i+1=j$同样会有贡献，而该方法统计不上，所以输出时直接加上就好。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 200005
#define inf 0x3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}//快读
inline int ran(){
static int seed=45562;
return seed=seed*48271LL%2147483647;
}//一个优化常数的随机数函数
int a[maxn],pos[maxn],ll[maxn],rr[maxn],n;
vector<int>lq[maxn],rq[maxn],li[maxn],ri[maxn];
//分别用来存询问左端点、右端点和ll、rr的位置情况
//vector可以用链式前向星代替，常数小。不过我懒了。。。
struct Question{
int l,r;
long long ans;
}q[maxn];
struct Treap{
#define ls(x) ls[x]
#define rs(x) rs[x]
int dat[maxn],ls[maxn],rs[maxn],ra[maxn],root,cnt;
void right(int &node){
int rec=ls(node);
ls(node)=rs(rec);
rs(rec)=node;
node=rec;
}
void left(int &node){
int rec=rs(node);
rs(node)=ls(rec);
ls(rec)=node;
node=rec;
}
void insert(int &node,int d){
if(！node){
node=++cnt;
dat[node]=d;
ra[node]=ran();
return;
}
if(dat[node]<d){
insert(rs(node),d);
if(ra[rs(node)]>ra[node])left(node);
}
else {
insert(ls(node),d);
if(ra[ls(node)]>ra[node])right(node);
}
}
int getpre(int d){
int ans=0,node=root;
while(node){
if(dat[node]<d)ans=max(ans,dat[node]),node=rs(node);
else node=ls(node);
}
return ans;
}
int getnex(int d){
int ans=n+1,node=root;
while(node){
if(dat[node]<d)node=rs(node);
else ans=min(ans,dat[node]),node=ls(node);
}
return ans;
}
}tr;//平衡树
#undef ls
#undef rs
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct Segment_Tree{
int dat[maxn<<2],tag[maxn<<2];
inline void update(int node){
dat[node]=dat[ls(node)]+dat[rs(node)];
}
inline void datadown(int l,int r,int node,int d){
dat[node]+=(r-l+1)*d;
tag[node]+=d;
}
inline void pushdown(int l,int r,int node){
int mid=l+r>>1;
datadown(l,mid,ls(node),tag[node]);
datadown(mid+1,r,rs(node),tag[node]);
tag[node]=0;
}
void add(int L,int R,int l,int r,int node){
if(L<=l&&R>=r){
dat[node]+=r-l+1;
++tag[node];
return;
}
if(tag[node])pushdown(l,r,node);
int mid=l+r>>1;
if(L<=mid)add(L,R,l,mid,ls(node));
if(R>mid)add(L,R,mid+1,r,rs(node));
update(node);
}
long long ask(int L,int R,int l,int r,int node){
if(L<=l&&R>=r)return (long long)dat[node];
if(tag[node])pushdown(l,r,node);
int mid=l+r>>1;
long long ans=0;
if(L<=mid)ans=ask(L,R,l,mid,ls(node));
if(R>mid)ans+=ask(L,R,mid+1,r,rs(node));
return ans;
}
}st1,st2,st3;//空间够大开三棵线段树QwQ
int main(){
n=read();
int m=read();
long long p1=read<long long>(),p2=read<long long>();
for(register int i=1;i<=n;++i){
a[i]=read();
pos[a[i]]=i;
}
sort(a+1,a+1+n);
for(register int i=n;i;--i){
int L=tr.getpre(pos[a[i]]),R=tr.getnex(pos[a[i]]);
ll[pos[a[i]]]=L;
rr[pos[a[i]]]=R;
if(L!=-inf)li[L].push_back(pos[a[i]]);
if(R!=inf)ri[R].push_back(pos[a[i]]);
tr.insert(tr.root,pos[a[i]]);
}
for(register int i=1;i<=m;++i)
q[i].l=read(),q[i].r=read(),lq[q[i].l].push_back(i),rq[q[i].r].push_back(i);
for(register int i=n;i;--i){
for(register int j=0;j<li[i].size();++j){
if(li[i][j]+1<rr[li[i][j]])st1.add(li[i][j]+1,rr[li[i][j]]-1,0,n+1,1);
st3.add(rr[li[i][j]],n+1,0,n+1,1);
}
for(register int j=0;j<lq[i].size();++j)
q[lq[i][j]].ans+=st1.ask(i,q[lq[i][j]].r,0,n+1,1)*p2+st3.ask(q[lq[i][j]].r,q[lq[i][j]].r,0,n+1,1)*p1;
}
for(register int i=1;i<=n;++i){
for(register int j=0;j<ri[i].size();++j)
if(ll[ri[i][j]]+1<ri[i][j])st2.add(ll[ri[i][j]]+1,ri[i][j]-1,0,n+1,1);
for(register int j=0;j<rq[i].size();++j)
q[rq[i][j]].ans+=st2.ask(q[rq[i][j]].l,i,0,n+1,1)*p2;
}
for(register int i=1;i<=m;++i)
printf("%d\n",q[i].ans+(long long)(q[i].r-q[i].l)*p1);
}
