I. Illuminated Ray Cast
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ vertical poles standing on a straight line at integer positions $$$x = 1,2,\dots,n$$$. The $$$i$$$-th pole has height $$$h_i$$$ and is located at $$$x = i$$$.

Sunlight comes from the left and travels in the direction of the vector $$$\vec{d} = (t_x, t_y)$$$ with $$$t_x \gt 0$$$. This means the rays propagate toward increasing $$$x$$$, with vertical slope determined by $$$t_y/t_x$$$.

A pole is ray cast (its top is directly lit) if its top lies strictly above the shadow envelope formed by all poles to its left.

  • The shadow envelope is the upper boundary traced by rays starting from the tops of earlier poles and extending rightward along $$$\vec{d}$$$.
  • If the top of a pole lies exactly on the envelope, then the pole is not ray cast (ties are considered blocked).

Your task is to count how many poles are ray cast.

Input

The first line contains $$$t$$$ ($$$1 \le t \le 150\,000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the number of poles.

The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^{9}$$$) — the heights of the poles.

The third line contains two integers $$$t_x$$$ and $$$t_y$$$ ($$$1 \le t_x \le 10^{9}$$$, $$$-10^{9} \le t_y \le 10^{9}$$$) — the components of the sunlight direction vector $$$\vec{d}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^{5}$$$.

Output

For each test case, print a single integer — the number of poles that are ray cast.

Example
Input
4
5
2 3 2 7 4
2 1
5
5 7 4 6 3
2 -1
4
5 5 5 5
3 0
3
3 10 7
1 -2
Output
3
2
1
2
Note

Figure 1 corresponds to the first test case with $$$h = [2,3,2,7,4], t_x = 2, t_y = 1$$$.

  • Poles 1, 2, and 4 are ray cast.
  • Poles 3 and 5 are not ray cast because they lie under the shadow envelope.

Figure 2 corresponds to the second test case with $$$h = [5,7,4,6,3], t_x = 2, t_y = -1$$$.

  • Poles 1 and 2 are ray cast.
  • Poles 3, 4, and 5 are not ray cast.
  • Notice that pole 4 is not ray cast even though a ray from pole 1 exactly meets its tip. By rule, equality with the shadow envelope does not count as lit — ties are considered blocked.