問題一覧 > 通常問題

No.1975 Zigzag Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : magstamagsta / テスター : LayCurseLayCurse
2 ProblemId : 6847 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-07 20:07:10

問題文

長さ $N$ の整数列 $A_1, A_2, \dots , A_N$ が与えられます。

この数列の空でない部分列は $2^N-1$ 個ありますが、それらのジグザグ度の和を $10^9+7$ で割った余りを求めてください。


また、長さ $M$ の整数列 $B_1, B_2, \dots , B_M$ のジグザグ度は

  • $B_i$ は $B_{i-1}, B_{i+1}$ のどちらよりも大きい
  • $B_i$ は $B_{i-1}, B_{i+1}$ のどちらよりも小さい

のどちらかの条件を満たす $i \ (2 \leq i \leq M-1)$ の個数として定義します。

制約

  • $\displaystyle 1 \leq N \leq 10^5$
  • $\displaystyle 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。 

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

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
4
1 4 2 3
出力
5

  • 部分列 $1,4,2$ のジグザグ度は $1$
  • 部分列 $1,4,3$ のジグザグ度は $1$
  • 部分列 $4,2,3$ のジグザグ度は $1$
  • 部分列 $1,4,2,3$ のジグザグ度は $2$

です。

これ以外の部分列のジグザグ度は $0$ なため、ジグザグ度の和は $5$ となります。

サンプル2
入力
1
1
出力
0

サンプル3
入力
5
28374282 182314219 928310293 28374282 928310293
出力
14

同じ数が含まれる場合もあります。

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