[Solution] Longest Strike solution codeforces

Longest Strike solution codeforces – Given an array 𝑎a of length 𝑛n and an integer 𝑘k, you are tasked to find any two numbers 𝑙l and 𝑟r (𝑙𝑟l≤r) such that:

  • For each 𝑥x (𝑙𝑥𝑟)(l≤x≤r)𝑥x appears in 𝑎a at least 𝑘k times (i.e. 𝑘k or more array elements are equal to 𝑥x).
  • The value 𝑟𝑙r−l is maximized.

[Solution] Longest Strike solution codeforces

If no numbers satisfy the conditions, output -1.

For example, if 𝑎=[11,11,12,13,13,14,14]a=[11,11,12,13,13,14,14] and 𝑘=2k=2, then:

  • for 𝑙=12l=12𝑟=14r=14 the first condition fails because 1212 does not appear at least 𝑘=2k=2 times.
  • for 𝑙=13l=13𝑟=14r=14 the first condition holds, because 1313 occurs at least 𝑘=2k=2 times in 𝑎a and 1414 occurs at least 𝑘=2k=2 times in 𝑎a.
  • for 𝑙=11l=11𝑟=11r=11 the first condition holds, because 1111 occurs at least 𝑘=2k=2 times in 𝑎a.

A pair of 𝑙l and 𝑟r for which the first condition holds and 𝑟𝑙r−l is maximal is 𝑙=13l=13𝑟=14r=14.

Input

The first line of the input contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers 𝑛n and 𝑘k (1𝑛21051≤n≤2⋅1051𝑘𝑛1≤k≤n) — the length of the array 𝑎a and the minimum amount of times each number in the range [𝑙,𝑟][l,r] should appear respectively.

Then a single line follows, containing 𝑛n integers describing the array 𝑎a (1𝑎𝑖1091≤ai≤109).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Longest Strike solution codeforces

For each test case output 22 numbers, 𝑙l and 𝑟r that satisfy the conditions, or “-1” if no numbers satisfy the conditions.

If multiple answers exist, you can output any.

Example
input

Copy
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4

[Solution] Longest Strike solution codeforces

output

Copy
13 14
1 3
-1
1 4

 

For Solution

Click here

Leave a Comment