You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。

千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

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

题目描述

奈文摩尔有 $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_2, \cdots, k_n$。

输入格式

第一行四个整数 $n,m,p_1,p_2$。

第二行 $n$ 个整数 $k_1, k_2,\cdots, k_n$。

接下来 $m$ 行,每行两个数 $a,b$，表示询问区间 $[a,b]$ 中的灵魂对会为影魔提供多少攻击力。

输出格式

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

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

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