問題一覧 > 通常問題

No.1975 Zigzag Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 87
作問者 : magsta / テスター : LayCurse
お気に入りにしたユーザー ProblemId : 6847 / 自分の提出
問題文最終更新日: 2022-06-07 20:07:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 347 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A_1, A_2, \dots , A_N$ of length $N$.

This sequence has $2^N-1$ non-empty subsequences. Find the sum of their zigzag degrees, modulo $10^9+7$.


The zigzag degree of an integer sequence $B_1, B_2, \dots , B_M$ of length $M$ is defined as the number of $i \ (2 \leq i \leq M-1)$ satisfying either of the following conditions:

  • $B_i$ is greater than both $B_{i-1}, B_{i+1}$
  • $B_i$ is less than both $B_{i-1}, B_{i+1}$

Constraints

  • $\displaystyle 1 \leq N \leq 10^5$
  • $\displaystyle 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
  • All inputs are integers.

Input

The input is given from standard input in the following format. 

$N$
$A_1 \ \ A_2 \ \dots \ A_N$

Output

Output the computed value, followed by a newline.

Sample

Sample 1
Input
4
1 4 2 3
Output
5

  • The zigzag degree of the subsequence $1,4,2$ is $1$
  • The zigzag degree of the subsequence $1,4,3$ is $1$
  • The zigzag degree of the subsequence $4,2,3$ is $1$
  • The zigzag degree of the subsequence $1,4,2,3$ is $2$

The zigzag degrees of all other subsequences are $0$, so the sum of the zigzag degrees is $5$.

Sample 2
Input
1
1
Output
0

Sample 3
Input
5
28374282 182314219 928310293 28374282 928310293
Output
14

The sequence may contain equal values.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。