{"raw_statement":[{"iden":"statement","content":"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 Al, Al + 1, ..., Ar with Ar, Ar - 1, ..., Al) to maximize the length of the longest non-decreasing subsequence of A. Find that maximal length and any inverting way to accomplish that mission.\n\nA non-decreasing subsequence of A with length m could be represented as Ax1, Ax2, ..., Axm with 1 ≤ x1 < x2 < ... < xm ≤ n and Ax1 ≤ Ax2 ≤ ... ≤ Axm.\n\nThe first line contains one integer T, indicating the number of test cases.\n\nThe following lines describe all the test cases. For each test case:\n\nThe first line contains one integer n.\n\nThe second line contains n integers A1, A2, ..., An without any space.\n\n1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 0 ≤ Ai ≤ 9 (i = 1, 2, ..., n).\n\nIt is guaranteed that the sum of n in all test cases does not exceed 2·105.\n\nFor 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.\n\nIn the first example, 864852302 after inverting [1, 8] is 032584682, one of the longest non-decreasing subsequences of which is 03588.\n\nIn the second example, 203258468 after inverting [1, 2] is 023258468, one of the longest non-decreasing subsequences of which is 023588.\n\n"},{"iden":"input","content":"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 A1, A2, ..., An without any space.1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 0 ≤ Ai ≤ 9 (i = 1, 2, ..., n).It is guaranteed that the sum of n in all test cases does not exceed 2·105."},{"iden":"output","content":"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."},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n \\in \\mathbb{Z} $ be the length of sequence $ A = (A_1, A_2, \\dots, A_n) $, where $ A_i \\in \\{0, 1, \\dots, 9\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 100 $  \n2. $ 1 \\leq n \\leq 10^5 $  \n3. $ 0 \\leq A_i \\leq 9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ \\sum_{\\text{all test cases}} n \\leq 2 \\cdot 10^5 $  \n\n**Objective**  \nFind an interval $ [l, r] $ with $ 1 \\leq l \\leq r \\leq n $, such that after reversing the subsequence $ A[l:r] $, the length of the longest non-decreasing subsequence (LNDS) of the resulting sequence is maximized.  \n\nLet $ m^* $ denote the maximum possible LNDS length over all such reversals.  \nOutput $ m^* $ and any pair $ (l, r) $ achieving it.","simple_statement":"Given an array of digits, you can reverse exactly one contiguous subarray to maximize the length of the longest non-decreasing subsequence. Find the maximum possible length and any subarray [l, r] that achieves it.","has_page_source":false}