D. K-Good Subsequences
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is too lazy to write an interesting story for this problem, so he just gave you a formal statement.

Define a $$$M$$$-sequence as a sequence of positive integers, each between $$$1$$$ and $$$M$$$ inclusive.

A $$$M$$$-sequence is called $$$K$$$-good if the absolute difference between any pair of adjacent elements is at most $$$K$$$. For example, $$$[1, 2, 3, 5, 5, 3, 2, 1]$$$ is $$$2$$$-good and $$$2024$$$-good, but not $$$1$$$-good. We also consider $$$M$$$-sequences of length $$$0$$$ or $$$1$$$ to be $$$K$$$-good.

Given positive integers $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$, and a $$$M$$$-sequence $$$a_1, \dots, a_N$$$ of length $$$N$$$, find the maximum possible number of elements in a $$$M$$$-sequence $$$b$$$, such that:

  • $$$b$$$ has $$$a$$$ as a prefix; and
  • Every $$$K$$$-good subsequence of $$$b$$$ has at most $$$L$$$ elements.

Recall that a subsequence of a sequence is obtained by deleting some elements (possibly all or none) from a sequence, without reordering the remaining elements.

Input

There are multiple test cases. The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$), the number of test cases.

The first line of each test case contains four integers $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$ ($$$0 \le N \le 2 \cdot 10^5$$$, $$$1 \le M \le 10^9$$$, $$$0 \le K \le 10^9$$$, $$$1 \le L \le 10^9$$$).

The second line of a test case contains $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le M$$$). If $$$N = 0$$$, then this line is skipped.

It is guaranteed that every $$$K$$$-good subsequence of $$$a$$$ has at most $$$L$$$ elements. Furthermore, the sum of $$$N$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output one line with the maximum number of elements in $$$b$$$. It can be shown that under the problem's constraints, the maximum always exists and does not exceed $$$9 \cdot 10^{18}$$$.

Scoring
  • ($$$5$$$ points) $$$M \le K + 1$$$.
  • ($$$5$$$ points) $$$K = 0$$$.
  • ($$$10$$$ points) $$$N = 0$$$.
  • ($$$15$$$ points) $$$N = 1$$$.
  • ($$$30$$$ points) The sum of each of $$$N$$$, $$$M$$$, $$$K$$$, and $$$L$$$ over all test cases does not exceed $$$3000$$$.
  • ($$$35$$$ points) No additional constraints.
Example
Input
3
3 3 1 3
1 3 2
0 5 2 3
7 7 2 3
1 4 2 7 7 1 6
Output
5
6
7
Note

In the first sample test case, one possible $$$M$$$-sequence $$$b$$$ is $$$[1, 3, 2, 3, 1]$$$, whose $$$1$$$-good subsequences, such as $$$[3, 2, 3]$$$ and $$$[3, 2, 1]$$$, all have length at most $$$L = 3$$$.

In the second sample test case, one possible $$$M$$$-sequence $$$b$$$ is $$$[1, 1, 5, 4, 2, 5]$$$, whose $$$2$$$-good subsequences, such as $$$[5, 4, 2]$$$ and $$$[1, 1, 2]$$$, all have length at most $$$L = 3$$$.

In the third sample test case, it can be shown that the only possible $$$b$$$ is $$$b = a$$$.