← 返回题目列表

Codeforces · 1647/F

F. 小圆和懒惰

中文机器翻译题面 查看原题

小圆已经懒得写图例了,所以让我们直接进入问题的正式描述。

整数数组 $$$a_1, a_2, \ldots, a_n$$$ 如果不为空并且其中有索引 $$$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]$$$ 不是子序列。

如果每个元素恰好属于一个子序列,并且每个子序列都是一座山,则将数组拆分为两个子序列称为良好。

给定一个由不同正整数 $$$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$$$ 都是成对不同的。

输出

在一行中,准确打印一个数字 - 所有良好分割中第一个和第二个子序列的不同最大值对的数量。

示例

输入 #1

4
1 2 4 3

输出 #1

3

输入 #2

8
2 12 13 7 14 6 11 8

输出 #2

4

输入 #3

7
9 5 3 10 2 6 8

输出 #3

0

输入#4

8
8 6 10 9 1 5 2 14

输出#4

0

注意

在第一个测试用例中,有 3 个可能的对:$$$(3, 4)$$$、$$$(2, 4)$$$、$$$(1, 4)$$$。它们是通过以下分区实现的:$$$[1, 2, 3], [4]$$$; $$$[4, 3], [1, 2]$$$; $$$[1]、[2、4、3]$$$