405809: GYM102114 H Hills And Valleys

Tauren has an integer sequence A of length n (1-based). He wants you to invert an interval [l, r] (1 ≤ l ≤ r ≤ n) of A (that is, replace A_l, A_l + 1, ..., A_r with A_r, A_r - 1, ..., A_l) to maximize the length of the longest non-decreasing subsequence of A. Find that maximal length and any inverting way to accomplish that mission.

A non-decreasing subsequence of A with length m could be represented as A_x1, A_x2, ..., A_xm with 1 ≤ x₁ < x₂ < ... < x_m ≤ n and A_x1 ≤ A_x2 ≤ ... ≤ A_xm.

The first line contains one integer T, indicating the number of test cases.

The following lines describe all the test cases. For each test case:

The first line contains one integer n.

The second line contains n integers A₁, A₂, ..., A_n without any space.

1 ≤ T ≤ 100, 1 ≤ n ≤ 10⁵, 0 ≤ A_i ≤ 9 (i = 1, 2, ..., n).

It is guaranteed that the sum of n in all test cases does not exceed 2·10⁵.

For each test case, print three space-separated integers m, l and r in one line, where m indicates the maximal length and [l, r] indicates the relevant interval to invert.

2
9
864852302
9
203258468

5 1 8
6 1 2

In the first example, 864852302 after inverting [1, 8] is 032584682, one of the longest non-decreasing subsequences of which is 03588.

In the second example, 203258468 after inverting [1, 2] is 023258468, one of the longest non-decreasing subsequences of which is 023588.