← 返回题目列表

AtCoder · past202109_n

N. 之字形序列

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

分数: 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