Range and Partition
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 1800
Tags: binary search, constructive algorithms, data structures, greedy, two pointers

Given an array $$$a$$$ of $$$n$$$ integers, find a range of values $$$[x, y]$$$ ($$$x \le y$$$), and split $$$a$$$ into exactly $$$k$$$ ($$$1 \le k \le n$$$) subarrays in such a way that:

- Each subarray is formed by several continuous elements of $$$a$$$, that is, it is equal to $$$a_l, a_{l+1}, \ldots, a_r$$$ for some $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).
- Each element from $$$a$$$ belongs to exactly one subarray.
- In each subarray the number of elements inside the range $$$[x, y]$$$ (inclusive) is strictly greater than the number of elements outside the range. An element with index $$$i$$$ is inside the range $$$[x, y]$$$ if and only if $$$x \le a_i \le y$$$.

Print any solution that minimizes $$$y - x$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$ and the number of subarrays required in the partition.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, print $$$k+1$$$ lines.

In the first line, print $$$x$$$ and $$$y$$$ — the limits of the found range.

Then print $$$k$$$ lines, the $$$i$$$-th should contain $$$l_i$$$ and $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — the limits of the $$$i$$$-th subarray.

You can print the subarrays in any order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, there should be only one subarray, which must be equal to the whole array. There are $$$2$$$ elements inside the range $$$[1, 2]$$$ and $$$0$$$ elements outside, if the chosen range is $$$[1, 1]$$$, there will be $$$1$$$ element inside ($$$a_1$$$) and $$$1$$$ element outside ($$$a_2$$$), and the answer will be invalid.

In the second test, it is possible to choose the range $$$[2, 2]$$$, and split the array in subarrays $$$(1, 3)$$$ and $$$(4, 4)$$$, in subarray $$$(1, 3)$$$ there are $$$2$$$ elements inside the range ($$$a_2$$$ and $$$a_3$$$) and $$$1$$$ element outside ($$$a_1$$$), in subarray $$$(4, 4)$$$ there is only $$$1$$$ element ($$$a_4$$$), and it is inside the range.

In the third test, it is possible to choose the range $$$[5, 5]$$$, and split the array in subarrays $$$(1, 4)$$$, $$$(5, 7)$$$ and $$$(8, 11)$$$, in the subarray $$$(1, 4)$$$ there are $$$3$$$ elements inside the range and $$$1$$$ element outside, in the subarray $$$(5, 7)$$$ there are $$$2$$$ elements inside and $$$1$$$ element outside and in the subarray $$$(8, 11)$$$ there are $$$3$$$ elements inside and $$$1$$$ element outside.

Example input:
3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1

Example output:
1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11

Editorial:
Focus on how to solve the problem for a fixed interval $$$[x,y]$$$:
Let us define an array $$$b$$$ such that $$$b_i = 1$$$ if $$$x \le a_i \le y$$$ or $$$b_i = -1$$$ otherwise, for all $$$1\le i\le n$$$.
Let's define $$$psum_i$$$ as $$$b_1 + b_2 + ... + b_i$$$.
We need to find a partition on $$$k$$$ subarrays with positive sum of $$$b_i$$$.
The sum of a subarray $$$[l,r]$$$ is $$$b_l+b_{l+1}+...+b_r = psum_r-psum_{l-1}$$$. Then a subarray is valid if $$$psum_r > psum_{l-1}$$$.
We need to find an increasing sequence of $$$psum$$$ of length $$$k+1$$$ starting at $$$0$$$ and ending at $$$n$$$.
Let's define $$$firstocc_x$$$ to be the first occurrence of the integer $$$x$$$ in $$$psum$$$.
If $$$psum_n < k$$$ there will be no valid sequence, otherwise the sequence $$$0, firstocc_1, firstocc_2, ..., firstocc_{k-1}, n$$$ will satisfy all constraints.
Note that, since $$$|psum_i-psum_{i-1}| = 1$$$, for $$$i>0$$$, then $$$firstocc_v$$$ exists and $$$firstocc_v < firstocc_{v+1}$$$ for $$$0\leq v \leq psum_n$$$.
This solves the problem for a fixed interval.
It remains to find the smallest interval $$$[x,y]$$$ such that $$$psum_n \geq k$$$.
For a given interval $$$[x,y]$$$, since $$$psum_n = b_1 + b_2 + ... + b_n$$$, $$$psum_n$$$ will be equal to the number of elements of $$$a$$$ inside the interval minus the number of elements outside.
Then for each $$$x$$$, it is possible to find the smallest $$$y$$$ such that $$$psum_n \geq k$$$ using binary search or two pointers.
It is also possible to note that: $$$$$$psum_n \geq k$$$$$$ $$$$$$\sum\limits_{i=1}^n b_i \geq k$$$$$$ $$$$$$\sum\limits_{i=1}^n (-1 + 2\cdot [x\le a_i\le y]) \geq k$$$$$$ $$$$$$\sum\limits_{i=1}^n [x\le a_i\le y] \geq \lceil{\frac{k+n}{2}}\rceil$$$$$$
We need to find the smallest interval with at least $$$\lceil{\frac{k+n}{2}}\rceil$$$ inside, let $$$A$$$ be the array $$$a$$$ sorted, the answer is the minimum interval among all intervals $$$[A_i, A_{i+\lceil{\frac{k+n}{2}}\rceil-1}]$$$ for $$$1 \leq i \leq n - \lceil{\frac{k+n}{2}}\rceil+1$$$.
Complexity: $$$O(n\log{n})$$$ if solved with the previous formula or binary search, or $$$O(n)$$$ is solved with two pointers.