CF2268D AghaBalaSar and Hamed

给定一个长度为 $n$ 的排列 $^{\text{∗}}$ $p$。 对于每个下标 $i$，一步之内可以移动到： - 任意满足 $j \lt i$ 的下标，或 - 满足 $j \gt i$ 且 $p_j \gt p_i$ 的最小下标（如果这样的下标存在）。 换句话说： - 左边的位置随便挑，想去哪儿就去哪儿。 - 右边则只能前往数值严格大于当前位置数值的 最近 位置。 对于每一对下标 $(i,j)$，令 $f(i,j)$ 表示从 $i$ 移动到 $j$ 所需的最少步数。注意，如果无法从 $i$ 到达 $j$，则 $f(i,j)=0$。 你的任务是计算： $$\sum_{1 \le i,j \le n} f(i,j).$$ $^{\text{∗}}$ 长度为 $n$ 的排列是一个由 $n$ 个互不相同的整数构成的数组，这些整数恰好是从 $1$ 到 $n$ 的任意排列。例如，$[2,3,1,5,4]$ 是一个排列；而 $[1,2,2]$ 不是排列，因为数组中 $2$ 出现了两次；$[1,3,4]$ 也不是排列，因为 $n=3$，但数组中出现了 $4$。

每个测试包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示 $p$ 的长度。 第二行包含 $n$ 个互不相同的整数 $p_1,p_2,\ldots,p_n$（$1\le p_i\le n$），表示数组 $p$ 的元素。 保证所有测试用例的 $n$ 之和不超过 $10^6$。

对于每组测试用例，输出一个整数，即 $\sum\limits_{1 \le i,j \le n} f(i,j)$ 的值。

在第一组测试用例中，$f(1, 2) + f(2, 1) = 1 + 1 = 2$。 在第二组测试用例中，$f(1, 2) + f(2, 1) = 0 + 1 = 1$。 在第三组测试用例中，$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 0 + 1 + 0 + 1 + 1 = 4$。 在第四组测试用例中，$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 2 + 1 + 1 + 1 + 1 = 7$。 由 ChatGPT 翻译。