题目描述

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。

奈文摩尔有 $n$ 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 $1$ 到 $n$。第 $i$ 个灵魂的战斗力为 $k_i$，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 $i, j(i<j)$ 来说，若不存在 $k_s(i<s<j)$ 大于 $k_i$ 或者 $k_j$，则会为影魔提供 $p_1$ 的攻击力（可理解为：当 $j = i + 1$ 时，因为不存在满足 $i < s < j$ 的 $s$，从而 $k_s$ 不存在，这时提供 $p_1$ 的攻击力；当 $j > i + 1$ 时，若 $\max{k_s | i < s < j}\le \min(k_i, k_j)$，则提供 $p1$ 的攻击力）；另一种情况，令 $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$ 个询问。

样例

input

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

output

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$。