E - 小大小大……
Editorial
/
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
(1,2,\ldots,N) の順列 P=(p_1,p_2,\ldots,p_N) が与えられます。
P を 1 個以上の空でない連続部分列 X_1,X_2,\ldots,X_K に分割し、以下のように (m_1,m_2,\ldots,m_K) を定めました。
- i が奇数ならば m_i は X_i に含まれる値の最小値
- i が偶数ならば m_i は X_i に含まれる値の最大値
(m_1,m_2,\ldots,m_K) としてあり得るものの個数を (10^9+7) で割った余りを求めてください。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq p_i \leq N
- i \neq j ならば p_i \neq p_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 \ldots p_N
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
3
P を分割する方法は 4 通りあり、それぞれに対応する (m_1,m_2,\ldots,m_K) は以下の通りです。
- (1,2,3) に分割する。\min(1,2,3)= 1 なので対応する数列は (1) である。
- (1), (2,3) に分割する。\min(1)= 1, \max(2,3)=3 なので対応する数列は (1,3) である。
- (1,2),(3) に分割する。\min(1,2)= 1, \max(3) = 3 なので対応する数列は (1, 3) である。
- (1),(2),(3) に分割する。\min(1)= 1, \max(2)=2, \min(3)=3 なので対応する数列は (1,2,3) である。
以上より、 (m_1,m_2,\ldots,m_K) としてあり得るものは (1), (1,3), (1,2,3) の 3 個です。
入力例 2
5 5 4 1 3 2
出力例 2
15