Firefly Intervals

In this problem, you are given a row of n fireflies numbered from 1 to n. Each firefly has a unique brightness value forming a permutation of the integers from 1 to n. You are also given two integers k and m. A firefly interval is defined as any contiguous segment of the fireflies with at least k elements. For any interval from L to R (with R–L+1 ≥ k), its overall brightness value is defined as the m-th largest brightness among the fireflies in that interval.

You will be given Q queries. Each query contains a number x. For each query, your task is to count the number of firefly intervals whose overall brightness value is at least x. Formally, if we denote the brightness values in the interval [L, R] as \(a_L, a_{L+1}, \dots, a_R\), then let \(B\) be the multiset of these values sorted in descending order. The interval is valid if \(B[m] \ge x\) (i.e. in the sorted order, the \(m\)-th element is \(\ge x\)).

Note: An equivalent condition is that there are at least m fireflies in the interval with brightness \(\ge x\) and the length of the interval is at least k.

Input Format (see below):

inputFormat

The first line contains four integers n, Q, k, and m separated by spaces.

The second line contains n integers representing the brightness values of the fireflies in order. These values form a permutation of \(1, 2, \dots, n\).

Each of the following Q lines contains an integer x representing a query.

outputFormat

For each query, output a single integer on a new line: the number of firefly intervals whose overall brightness value is at least x.

sample

5 2 2 1
3 5 1 2 4
4
2

9
10