{"problem":{"name":"H. Hills And Valleys","description":{"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 l","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10211H"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10211H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}