{"problem":{"name":"Equal LIS","description":{"content":"You are given a permutation $P_1, P_2, \\dots, P_N$ of integers from $1$ to $N$. Is it possible to split it into $2$ subsequences, which have equal length of the Longest Increasing Subsequence? Formall","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc052_d"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P_1, P_2, \\dots, P_N$ of integers from $1$ to $N$. Is it possible to split it into $2$ subsequences, which have equal length of the Longest Increasing Subsequence?\nFormally speaking, your goal is to get two integer sequences $a$ and $b$ such that:\n\n*   Both $a$ and $b$ are subsequences of $P$.\n*   Each integer $i=1,2,\\cdots,N$ appears in exactly one of $a$ and $b$.\n*   (The length of a longest increasing subsequence of $a$) $=$ (The length of a longest increasing subsequence of $b$)\n\nDetermine if the objective is achievable.\nYou will be given $T$ test cases. Solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 2 \\cdot 10^5$\n*   $1 \\le N \\le 2 \\cdot 10^5$\n*   $P_1, P_2, \\dots, P_N$ is a permutation of integers from $1$ to $N$.\n*   The sum of $N$ over all test cases doesn't exceed $2 \\cdot 10^5$.\n\n## Input\n\nInput is given from Standard Input in the following format. The first line of input is as follows:\n\n$T$\n\nThen, $T$ test cases follow, each of which is in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc052_d","tags":[],"sample_group":[["5\n1\n1\n2\n2 1\n3\n1 2 3\n5\n1 3 5 2 4\n6\n2 3 4 5 6 1","NO\nYES\nNO\nYES\nNO\n\n$[1, 3, 5, 2, 4]$ can be split into $[1, 5]$ and $[3, 2, 4]$, both have $LIS$ of length 2.\nIt can be shown that there is no way to split $[2, 3, 4, 5, 6, 1]$ into $2$ subsequences with an equal length of $LIS$."]],"created_at":"2026-03-03 11:01:14"}}