Range and Partition Solution|Codeforces round #768 (div 2)

                                            Range and Partition

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

Input

The input consists of multiple test cases. The first line contains a single integer t$t$ (1≤t≤3⋅104$1\le t\le 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$n$ and k$k$ (1≤k≤n≤2⋅105$1\le k\le n\le 2\cdot {10}^5$) — the length of the array a$a$ and the number of subarrays required in the partition.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$) where ai$a_i$ is the i$i$-th element of the array.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

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

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

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

You can print the subarrays in any order.

Note

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

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

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

Solution:

1. // Never give up
2. // Code by the Great Adarsh
3. #include <bits/stdc++.h>
4. using namespace std;
5. #define ll long long int
6. #define INF 1e9
7. #define all(x) (x).begin(), (x).end()
8. int main()
9. {
10. ios_base::sync_with_stdio(false);
11. cin.tie(NULL);
12.  
13. int t;
14. cin >> t;
15. while (t--)
16. {
17. ll n;
18. cin >> n;
19. vector<ll> v(n+1);
20. for (int i = 1; i <= n; i++)
21. cin >> v[i];
22. ll i = n - 1;
23. ll ans = 0;
24. while (i >0)
25. {
26. if (v[i] == v[n])
27. i--;
28. else
29. {
30. ans++;
31. i -= (n - i);
32. }
33. }
34. cout << ans << endl;
35. }
36. return 0;
37. }