题目描述

给定一个长度为 $N$ 的排列 $a_i$，你可以执行若干次操作：

• 选择两个相邻的数，删除它们中较大的那个。

问最后可能得到序列的数量，答案对 $10^9+7$ 取模。

注意如果两个数中间所有的数被删除了，它们会变成相邻的。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $a_i$。

输出格式

输出一个整数代表答案。

3
2 3 1

3

4
2 1 4 3

6

提示

【样例解释】

对于第一组样例，以下为所有可能得到的序列：

• $[2,3,1]$
• $[\bold2,\bold3,1]\to[2,1]$
• $[\bold2,\bold3,1]→[\bold2,\bold1]→[1]$

对于第二组样例，以下为所有可能得到的序列：

• $[2,1,4,3]$
• $[\bold2,\bold1, 4, 3]\to[1, 4, 3]$
• $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[1, 3]$
• $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[\bold1,\bold3]\to[1]$
• $[2, 1,\bold4,\bold3]\to[2, 1, 3]$
• $[2, 1,\bold4,\bold3]\to[2,\bold1,\bold3]\to[2, 1]$

【数据范围】

本题采用捆绑测试。

• Subtask 1（8 points）：只存在一组数据，满足 $N=6$，$A=[2,5,1,3,4,6]$。
• Subtask 2（20 points）：$N\leq 200$。
• Subtask 3（13 points）：$N\leq 2000$，$A_i=i$。
• Subtask 4（9 points）：$A_i=i$。
• Subtask 5（23 points）：$N\leq 2000$。
• Subtask 6（27 points）：无特殊限制。

对于所有数据，$N\leq 3\times 10^5$，保证输入的 $a_i$ 能构成一个排列。