CF2165F Arctic Acquisition

给定一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$。 对于一个区间 $[l,r]$（$1\le l\le r\le n$），如果它包含一个 21435 子序列，则称其为一个“jagged”区间；也就是说，存在整数 $i_1,i_2,i_3,i_4,i_5$，使得 $l\le i_1

每组测试包含若干个测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 10^4$）。每组测试用例描述如下。 每组测试用例第一行包含一个整数 $n$（$1\le n\le10^6$），表示排列的长度。 第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每组测试用例，输出 jagged 区间的个数。

在第一个测试用例中，唯一的 jagged 区间是 $[1,5]$，因为它包含 $[2,1,4,3,5]$ 作为子序列。 在第三个测试用例中，区间 $[1,8]$ 是 jagged 的，因为它包含 $[9,6,11,10,13]$ 作为子序列，这就是一个 21435-子序列。 由 ChatGPT 5 翻译