Hills And Valleys

Tauren has an integer sequence $A$ of length $n$ (1-based). He wants you to invert an interval $[l, r]$ ($1 \le l \le r \le n$) of $A$, that is, replace $A_l, A_{l+1}, \ldots, A_r$ with $A_r, A_{r-1}, \ldots, A_l$, so that the length of the longest non-decreasing subsequence of $A$ is as large as possible. Find that maximal length and any interval whose inversion achieves it.

A non-decreasing subsequence of $A$ with length $m$ is $A_{x_1}, A_{x_2}, \ldots, A_{x_m}$ with $1 \le x_1 < x_2 < \ldots < x_m \le n$ and $A_{x_1} \le A_{x_2} \le \ldots \le A_{x_m}$.

The first line contains one integer $T$, the number of test cases. Each test case is given as follows. The first line contains one integer $n$. The second line contains $n$ integers $A_1, A_2, \ldots, A_n$ written without spaces.

Constraints: $1 \le T \le 100$, $1 \le n \le 10^5$, $0 \le A_i \le 9$ for $i = 1, 2, \ldots, n$. The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, print three integers $m$, $l$, and $r$ separated by spaces on one line, where $m$ is the maximal length and $[l, r]$ is the interval to invert.

In the first example, 864852302 becomes 032584682 after inverting $[1, 8]$, and one of its longest non-decreasing subsequences is 03588. In the second example, 203258468 becomes 023258468 after inverting $[1, 2]$, and one of its longest non-decreasing subsequences is 023588.