Soul Pair Attack Power

You are given n souls arranged in a row with indices from \(1\) to \(n\). The \(i\)-th soul has combat power \(k_i\), and the combat powers form a permutation of \(\{1,2,\ldots,n\}\). For every pair of souls \((i,j)\) with \(i<j\), the pair contributes to the overall attack power according to the following rules:

• If there is no soul \(s\) with \(i<s k_i\) or \(k_s > k_j\) (i.e. every soul between them has combat power smaller than both \(k_i\) and \(k_j\)), then the pair contributes \(p_1\) attack power. Equivalently, if \(j=i+1\) (adjacent souls) the condition trivially holds.
• Otherwise, let \(c = \max\{k_{i+1}, k_{i+2}, \ldots, k_{j-1}\}\). If \(c\) satisfies \(k_i < c < k_j\) or \(k_j < c < k_i\) (i.e. \(c\) lies strictly between \(k_i\) and \(k_j\)), then the pair contributes \(p_2\) attack power.
• In all other cases, the pair provides no attack power.

Your task is to answer q queries. In each query you are given two integers \(a\) and \(b\), and you should compute the total attack power provided by all pairs \((i,j)\) with \(a \le i < j \le b\), according to the above rules.

Note: The array \(k_1,k_2,\ldots,k_n\) is a permutation of \(\{1,2,\ldots,n\}\).

inputFormat

The first line contains three integers \(n\), \(p_1\) and \(p_2\) separated by spaces.

The second line contains \(n\) distinct integers \(k_1,k_2,\ldots,k_n\) representing the combat powers (a permutation of \(\{1,\ldots,n\}\)).

The third line contains a single integer \(q\), the number of queries.

Each of the next \(q\) lines contains two integers \(a\) and \(b\) (with \(1 \le a < b \le n\)), describing a query.

outputFormat

For each query, output a single line containing the total attack power provided by all soul pairs \((i,j)\) with \(a \le i < j \le b\).

sample

5 10 5
2 4 1 5 3
3
1 5
2 4
3 5

55
30
20