Problem A
Max Arithmetic Subsequence
You are given a strictly increasing array of $n$ numbers $0\leq a_1<a_2<\ldots <a_ n \leq 10^{18}$. Define an arithmetic progression subsequence as a series of indices $i_1<i_2<\ldots <i_ k$ such that $a_{i_2}-a_{i_1} = a_{i_3}-a_{i_2}\ldots = a_{i_ k}-a_{i_{k-1}}$.
A constant $c$ is also given. Does the maximum length arithmetic progression subsequence of array $a$ contain strictly greater than $n/ c$ elements? If yes, print the maximum length of all arithmetic progression subsequences, otherwise, print $-1$.
Input
The first line contains one integer $t$ $(1\leq t \leq 1\, 000)$ — the number of test cases. Then $t$ cases follow.
The first line of each test case contains two integers n and c $(2\leq n\leq 100\, 000, 2 \leq c \leq 5)$ — the length of the array, and the minimum ratio for the arithmetic subsequence length.
The second line of each test case contains n integers $a_1,a_2,\ldots ,a_ n$ $(0\leq a_ i\leq 10^{18})$ — the array given in the problem.
It’s guaranteed that the sum of $n$ over all test cases doesn’t exceed $100\, 000$.
Output
For each test case, output a single integer — the answer to the problem.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 2 0 1 3 5 4 2 0 1 3 4 9 2 1 3 4 5 9 15 21 22 27 |
3 -1 5 |
