← 返回题目列表

AtCoder · maximum_cup_2023_e

E. 小尺寸大……

中文机器翻译题面 查看原题

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