CF1647F Madoka and Laziness

Madoka 太懒了，不想写题目背景，所以我们直接进入问题的正式描述。 一个整数数组 $a_1, a_2, \ldots, a_n$ 被称为“hill”（山峰），如果它非空，并且存在一个下标 $i$，满足：$a_1 < a_2 < \ldots < a_i > a_{i+1} > a_{i+2} > \ldots > a_n$。 如果序列 $x$ 可以通过从序列 $y$ 中删除若干（可以为零或全部）元素，并保持剩余元素的顺序得到，则称 $x$ 是 $y$ 的一个子序列。例如，对于数组 $[69, 1000, 228, -7]$，数组 $[1000, -7]$ 是其子序列，而 $[1]$ 和 $[-7, 1000]$ 不是。 如果将一个数组拆分成两个子序列，且每个元素恰好属于一个子序列，并且这两个子序列都是 hill，则称这样的拆分是“good”（好的）。 给定一个由互不相同的正整数组成的数组 $a_1, a_2, \ldots, a_n$，请你计算所有好的拆分中，第一和第二个子序列的最大值所组成的不同数对的数量。仅顺序不同的数对视为相同。

输入的第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$），表示数组的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组的元素。保证所有 $a_i$ 两两不同。

输出一行，包含一个整数，表示所有好的拆分中，第一和第二个子序列的最大值所组成的不同数对的数量。

在第一个测试用例中，有 3 种可能的数对：$(3, 4)$、$(2, 4)$、$(1, 4)$。它们分别由以下拆分方式得到：$[1, 2, 3], [4]$；$[4, 3], [1, 2]$；$[1], [2, 4, 3]$。 由 ChatGPT 4.1 翻译