AT_past202109_n ジグザグな数列

[problemUrl]: https://atcoder.jp/contests/past202109-open/tasks/past202109_n 以下の $ 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) $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ A $ の空でない部分列のうち、ジグザグな数列であるようなものの個数を $ (10^9+7) $ で割った余りを出力せよ。

### 注意 この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力は全て整数である。 ### Sample Explanation 1 $ A $ の空でない部分列は以下の $ 7 $ つです。そのうちジグザグな数列であるようなものは、星印で示された $ 4 $ つです。 - $ (1) $ - $ (3) $ - $ (2) $ - $ (1,3) $ $ \cdots $ ☆ - $ (1,2) $ $ \cdots $ ☆ - $ (3,2) $ $ \cdots $ ☆ - $ (1,3,2) $ $ \cdots $ ☆ ### Sample Explanation 2 $ 2 $ つの部分列は列として同じであっても、取り出す位置が異なる場合は区別されることに注意してください。 このケースにおいて、$ A $ の部分列であってかつジグザグな数列であるようなものは $ (1,3) $ と $ (1,3) $ の $ 2 $ つです。 ### Sample Explanation 3 答えは $ 0 $ になることもあります。