Description

Nevermore has $n$ souls. Inside the vast body of the Shadow Fiend, they can line up in a row, labeled from left to right $1$ to $n$. The $i$-th soul has combat power $k_i$, and souls provide attack power for the Shadow Fiend in the form of pairs. For a soul pair $i, j$ with $i < j$, if there is no $k_s$ with $i < s < j$ that is greater than $k_i$ or greater than $k_j$, then it provides $p_1$ attack power. In another case, let $c$ be the maximum of $k_{i + 1}, k_{i + 2}, \cdots, k_{j - 1}$. If $c$ satisfies $k_i < c < k_j$, or $k_j < c < k_i$, then it provides $p_2$ attack power. When such a $c$ does not exist, it naturally does not provide this $p_2$ attack power. In all other cases, the pair does not provide any attack power.

Shadow Fiend’s close friend Lifestealer visited him one day and was captivated by these souls. He wants to know, for any interval $[a, b]$, how much attack power is provided by the soul pairs within these intervals, that is, consider the sum of the attack power provided by all soul pairs $i, j$ satisfying $a \le i < j \le b$.

Incidentally, the souls’ combat powers form a permutation of $1$ to $n$: $k_1, k_2, \cdots, k_n$.

Input Format

The first line contains four integers $n, m, p_1, p_2$.

The second line contains $n$ integers $k_1, k_2, \cdots, k_n$.

Then there are $m$ lines. Each line contains two integers $a, b$, representing a query asking how much attack power is provided by the soul pairs within the interval $[a, b]$.

Output Format

Output $m$ lines, each containing one answer, corresponding to the $m$ queries in order.

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

Hint

For $30\%$ of the testdata, $1 \le n, m \le 500$.

For another $30\%$ of the testdata, $p_1 = 2 p_2$.

For $100\%$ of the testdata, $1 \le n, m \le 200000$, $1 \le p_1, p_2 \le 1000$.

Translated by ChatGPT 5