配点 : 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