CF1647F.Madoka and Laziness

Madoka has become too lazy to write a legend, so let's go straight to the formal description of the problem.

An array of integers $a_1, a_2, \ldots, a_n$ is called a hill if it is not empty and there is an index $i$ in it, for which the following is true: $a_1 \lt a_2 \lt \ldots \lt a_i \gt a_{i + 1} \gt a_{i + 2} \gt \ldots \gt a_n$.

A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements keeping the order of the other elements. For example, for an array $[69, 1000, 228, -7]$ the array $[1000, -7]$ is a subsequence, while $[1]$ and $[-7, 1000]$ are not.

Splitting an array into two subsequences is called good if each element belongs to exactly one subsequence, and also each of these subsequences is a hill.

You are given an array of distinct positive integers $a_1, a_2, \ldots a_n$. It is required to find the number of different pairs of maxima of the first and second subsequences among all good splits. Two pairs that only differ in the order of elements are considered same.

魔理沙已经懒到懒得写题面说明了，所以我们直接进入问题的形式化描述。

一个整数数组 $a_1, a_2, \ldots, a_n$ 被称为山形数组（hill），当且仅当它非空，且存在某个下标 $i$，使得以下条件成立：

$$a_1 \lt a_2 \lt \ldots \lt a_i \gt a_{i + 1} \gt a_{i + 2} \gt \ldots \gt a_n.$$

序列 $x$ 是序列 $y$ 的子序列（subsequence），当且仅当 $x$ 可通过从 $y$ 中删除若干（可能为零个或全部）元素、同时保持其余元素的相对顺序而得到。例如，对于数组 $[69, 1000, 228, -7]$，数组 $[1000, -7]$ 是其子序列，而 $[1]$ 和 $[-7, 1000]$ 则不是。

将一个数组划分为两个子序列被称为好的划分（good split），当且仅当每个元素恰好属于其中一个子序列，且这两个子序列均为山形数组。

给定一个由互异正整数组成的数组 $a_1, a_2, \ldots, a_n$。要求计算：在所有好的划分中，第一个子序列与第二个子序列的峰顶（即各自山形数组中的最大值）构成的无序对的不同种类总数。注意：仅顺序不同的两个对（如 $(x,y)$ 与 $(y,x)$）视为同一对。

The first line of input contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$) — array size.

The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array. It is guaranteed that all $a_i$ are pairwise distinct.

输入的第一行包含一个整数 $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$ 两两互不相同。

In a single line, print exactly one number — the number of different pairs of maxima of the first and second subsequences among all good splits.

在一行中，精确输出一个数字——即在所有合法划分中，第一子序列与第二子序列的最大值所构成的不同数对的个数。

In the first test case there are 3 possible pairs: $(3, 4)$, $(2, 4)$, $(1, 4)$. And they are achieved with the following partitions: $[1, 2, 3], [4]$; $[4, 3], [1, 2]$; $[1], [2, 4, 3]$

在第一个测试用例中，共有 3 种可能的数对：$(3, 4)$、$(2, 4)$、$(1, 4)$。它们分别通过以下划分方式实现：$[1, 2, 3], [4]$；$[4, 3], [1, 2]$；$[1], [2, 4, 3]$。