分数: 6 点
警告
2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
一系列数字, B,称为 之字形 当满足以下两个条件之一时,其中 |B| 表示元素的数量 B.
- B 的长度至少为 2,并且以下内容适用于每个 i i\ (1 \leq i \lt |B|).
- B_i \lt B_{i+1} if i 是奇数;
- B_i \gt B_{i+1} if i 是偶数。
- B 的长度至少为 2,并且以下内容适用于每个 i i\ (1 \leq i \lt |B|).
- B_i \gt B_{i+1} if i 是奇数;
- B_i \lt B_{i+1} if i 是偶数。
给你一个序列 A 长度 N。其中 2^N-1 的非空(不一定连续)子序列 A,有多少个锯齿形?
打印计数模数 (10^9+7).
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印 的非空子序列中锯齿形序列的数量 A,模数 (10^9+7).
示例输入 1
3 1 3 2
示例输出 1
4
A 有七个非空子序列,如下所示。其中,标有星号的四个序列是锯齿形的。
- (1)
- (3)
- (2)
- (1,3) \cdots ☆
- (1,2) \cdots ☆
- (3,2) \cdots ☆
- (1,3,2) \cdots ☆
示例输入 2
3 1 3 3
示例输出 2
2
请注意,如果两个子序列源自不同的位置,即使这些序列本身相同,它们也会被区分。
在这种情况下,两个子序列 A 之字形是 (1,3) 和 (1,3).
示例输入 3
4 2 2 2 2
示例输出 3
0
答案可能是 0.
示例输入 4
6 83 65 79 54 88 69
示例输出 4
44