← 返回题目列表

Codeforces · 1693/D

D. Decinc 除法

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

如果 $$$a$$$ 可以通过删除递减子序列(可能为空)来递增,那么我们将 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ 的数组 $$$a$$$ 称为 Decinc。

- 例如,如果$$$a = [3, 2, 4, 1, 5]$$$,我们可以从$$$a$$$中删除递减子序列$$$[a_1, a_4]$$$,得到递增的$$$a = [2, 4, 5]$$$。

您将获得从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$p$$$。求 $$$1 \le l \le r \le n$$$ 的整数对 $$$(l, r)$$$ 的数量,使得 $$$p[l \ldots r]$$$ ($$$p$$$ 从 $$$l$$$ 到 $$$r$$$ 的子数组)是 Decinc 数组。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$p$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, 所有 $$$p_i$$$ 都是不同的) — 排列的元素。

输出

输出整数对 $$$(l, r)$$$ 的数量,使得 $$$p[l \ldots r]$$$ ($$$p$$$ 从 $$$l$$$ 到 $$$r$$$ 的子数组)是 Decinc 数组。 $$$(1 \le l \le r \le n)$$$

示例

输入 #1

3
2 3 1

输出 #1

6

输入 #2

6
4 5 2 6 1 3

输出 #2

19

输入 #3

10
7 10 1 8 3 9 2 4 6 5

输出 #3

39

注意

在第一个示例中,所有子数组都是 Decinc。

在第二个示例中,除了 $$$p[1 \ldots 6]$$$ 和 $$$p[2 \ldots 6]$$$ 之外的所有子数组都是 Decinc。