[AH2017/HNOI2017]影魔

题目背景

影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。 千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。 每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。

题目描述

奈文摩尔有 $n$ 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 $1$ 到 $n$。第 $i$ 个灵魂的战斗力为 $k_i$,灵魂们以点对的形式为影魔提供攻击力。对于灵魂对 $i, j\ (i<j)$ 来说,若不存在 $k_s\ (i<s<j)$ 大于 $k_i$ 或者 $k_j$,则会为影魔提供 $p_1$ 的攻击力。另一种情况,令 $c$ 为 $k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}$ 的最大值,若 $c$ 满足:$k_i < c < k_j$,或者 $k_j < c < k_i$,则会为影魔提供 $p_2$ 的攻击力,当这样的 $c$ 不存在时,自然不会提供这 $p_2$ 的攻击力;其他情况的点对,均不会为影魔提供攻击力。 影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间 $[a, b]$,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑所有满足 $a\le i<j\le b$ 的灵魂对 $i, j$ 提供的攻击力之和。 顺带一提,灵魂的战斗力组成一个 $1$ 到 $n$ 的排列:$k_1, k_1, \cdots, k_n$。

输入输出格式

输入格式


第一行四个整数 $n,m,p_1,p_2$。 第二行 $n$ 个整数 $k_1, k_2,\cdots, k_n$。 接下来 $m$ 行,每行两个数 $a,b$,表示询问区间 $[a,b]$ 中的灵魂对会为影魔提供多少攻击力。

输出格式


共输出 $m$ 行,每行一个答案,依次对应 $m$ 个询问。

输入输出样例

输入样例 #1

10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5

输出样例 #1

30
39
4
13
16

说明

对于 $30\%$ 的数据,$1\le n, m\le 500$。 另有 $30\%$ 的数据,$p_1 = 2p_2$。 对于 $100\%$ 的数据,$1\le n,m\le 200000, 1\le p_1, p_2\le 1000$。