CF1630B.Range and Partition

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$.

给定一个包含 $n$ 个整数的数组 $a$，请找出一个值域区间 $[x, y]$（满足 $x \le y$），并将 $a$ 恰好划分为 $k$（$1 \le k \le n$）个子数组，使得：

• 每个子数组由 $a$ 中若干连续的元素构成，即形如 $a_l, a_{l+1}, \ldots, a_r$（其中 $1 \leq l \leq r \leq n$）；
• $a$ 中每个元素恰好属于一个子数组；
• 在每个子数组中，落在区间 $[x, y]$（含端点）内的元素个数严格大于落在该区间外的元素个数；元素 $a_i$ 落在区间 $[x, y]$ 内当且仅当 $x \le a_i \le y$。

请输出任意一组使 $y - x$ 最小的解。

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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 3 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2 \cdot 10^5$），分别表示数组 $a$ 的长度以及划分中所需子数组的个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），其中 $a_i$ 是数组的第 $i$ 个元素。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot10^5$。

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.

对于每个测试用例，输出 $k+1$ 行。

第一行输出 $x$ 和 $y$ —— 所找到区间的左右端点。

随后输出 $k$ 行，其中第 $i$ 行应包含 $l_i$ 和 $r_i$（满足 $1\leq l_i \leq r_i \leq n$）—— 第 $i$ 个子数组的左右端点。

子数组的输出顺序可以任意。

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.

在第一个测试用例中，只能有一个子数组，且该子数组必须等于整个数组。若选择的范围为 $[1, 2]$，则范围内有 $2$ 个元素，范围外有 $0$ 个元素；若选择的范围为 $[1, 1]$，则范围内有 $1$ 个元素（即 $a_1$），范围外有 $1$ 个元素（即 $a_2$），此时答案无效。

在第二个测试用例中，可以选择范围 $[2, 2]$，并将数组划分为子数组 $(1, 3)$ 和 $(4, 4)$：在子数组 $(1, 3)$ 中，范围内有 $2$ 个元素（即 $a_2$ 和 $a_3$），范围外有 $1$ 个元素（即 $a_1$）；在子数组 $(4, 4)$ 中，仅有 $1$ 个元素（即 $a_4$），且该元素在范围内。

在第三个测试用例中，可以选择范围 $[5, 5]$，并将数组划分为子数组 $(1, 4)$、$(5, 7)$ 和 $(8, 11)$：在子数组 $(1, 4)$ 中，范围内有 $3$ 个元素，范围外有 $1$ 个元素；在子数组 $(5, 7)$ 中，范围内有 $2$ 个元素，范围外有 $1$ 个元素；在子数组 $(8, 11)$ 中，范围内有 $3$ 个元素，范围外有 $1$ 个元素。