/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
以下の 2 つの条件のうち、いずれかを満たす数列 B を「ジグザグな数列」と定義します。ここで、|B| は B の要素数を表します。
- 長さが 2 以上であり、かつ、全ての i\ (1 \leq i \lt |B|) について以下が成り立つ。
- i が奇数なら B_i \lt B_{i+1}
- i が偶数なら B_i \gt B_{i+1}
- 長さが 2 以上であり、かつ、全ての i\ (1 \leq i \lt |B|) について以下が成り立つ。
- i が奇数なら B_i \gt B_{i+1}
- i が偶数なら B_i \lt B_{i+1}
長さ N の数列 A が与えられます。A の空でない（連続するとは限らない）部分列は 2^N-1 個ありますが、そのうちジグザグな数列はいくつありますか？
個数を (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 の空でない部分列は以下の 7 つです。そのうちジグザグな数列であるようなものは、星印で示された 4 つです。
- (1)
- (3)
- (2)
- (1,3) \cdots ☆
- (1,2) \cdots ☆
- (3,2) \cdots ☆
- (1,3,2) \cdots ☆
入力例 2
3 1 3 3
出力例 2
2
2 つの部分列は列として同じであっても、取り出す位置が異なる場合は区別されることに注意してください。
このケースにおいて、A の部分列であってかつジグザグな数列であるようなものは (1,3) と (1,3) の 2 つです。
入力例 3
4 2 2 2 2
出力例 3
0
答えは 0 になることもあります。
入力例 4
6 83 65 79 54 88 69
出力例 4
44
Score : 6 points
Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
A sequence of numbers, B, is called zigzag when it satisfies one of the following two conditions, where |B| denotes the number of elements in B.
- B has a length of at least 2, and the following holds for every i i\ (1 \leq i \lt |B|).
- B_i \lt B_{i+1} if i is odd;
- B_i \gt B_{i+1} if i is even.
- B has a length of at least 2, and the following holds for every i i\ (1 \leq i \lt |B|).
- B_i \gt B_{i+1} if i is odd;
- B_i \lt B_{i+1} if i is even.
You are given a sequence A of length N. Among the 2^N-1 non-empty (not necessarily contiguous) subsequences of A, how many are zigzag?
Print the count modulo (10^9+7).
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the number of zigzag sequences among the non-empty subsequences of A, modulo (10^9+7).
Sample Input 1
3 1 3 2
Sample Output 1
4
A has seven non-empty subsequences shown below. Among them, the four sequences marked with stars are zigzag.
- (1)
- (3)
- (2)
- (1,3) \cdots ☆
- (1,2) \cdots ☆
- (3,2) \cdots ☆
- (1,3,2) \cdots ☆
Sample Input 2
3 1 3 3
Sample Output 2
2
Note that two subsequences are distinguished if they originate from different positions, even if these sequences are the same in themselves.
In this case, the two subsequences of A that are zigzag are (1,3) and (1,3).
Sample Input 3
4 2 2 2 2
Sample Output 3
0
The answer may be 0.
Sample Input 4
6 83 65 79 54 88 69
Sample Output 4
44