Given a permutation $a$ consisting of integers from $1$ to $n$.
For a pair of indices $i < j$, with $c = \text{max}(a_{i+1}, a_{i+2}, \ldots, a_{j-1})$, the value of this pair is defined as:
- $x$ if $c \leq \text{min}(a_i, a_j)$ or $i = j - 1$.
- $y$ if $a_i < c < a_j$ or $a_i > c > a_j$.
- $0$ in all other cases.
Given $q$ queries $l, r$, calculate the total value of all pairs $(a, b)$ such that $l \leq a < b \leq r$.
### Input
- The first line contains four integers $n, q, x, y$.
- The second line contains $n$ integers representing the permutation $a$.
- The next $q$ lines each contain two integers $l, r$ representing a query.
### Output
- For each query, print the total value of all pairs that satisfy the condition.
### Constraints
- $1 \leq n, q \leq 2 \times 10^5$.
- $1 \leq x, y \leq 1000$.
### Example
Input:
```
10 5 2 3
9 3 5 4 10 7 6 8 1 2
1 7
1 5
1 9
5 9
1 3
```
Output:
```
27
20
38
18
6
```
### Subtasks
- Subtask 1 (30% of the points): $1 \leq n, q \leq 500$.
- Subtask 2 (30% of the points): $x = 2 \times y$.
- Subtask 3 (40% of the points): No additional constraints.
