### 问题描述 定义一个长为 $n$ $(n \geq 3)$ 的数组是交错的，当且仅当对于任意的 $2 \leq i \leq n-1$，都有 $a_{i-1} < a_i$，$a_{i+1} < a_i$ 或 $a_{i-1} > a_i$，$a_{i+1} > a_i$。 现在有一个长为 $n$ 的数组 $b$，求有多少数组 $a$ 满足对于任意的 $1 \leq i \leq n$，都有 $1 \leq a_i \leq b_i$，且数组 $a$ 是交错的。答案对 $10^9+7$ 取模。 ### 输入格式 输入第一行包含一个正整数 $n$，表示数组 $a$ 和 $b$ 的长度。 输入第二行包含 $n$ 个正整数 $b_1,b_2, \cdots ,b_n$，表示数组 $b$。 ### 输出格式 输出满足条件的数组 $a$ 的总数。答案对 $10^9+7$ 取模。 ### 样例输入 ```text 3 2 3 2 ``` ### 样例输出 ```text 6 ``` ### 说明 可能的数组 $a$ 有 $(1,2,1)$，$(1,3,1)$，$(1,3,2)$，$(2,1,2)$，$(2,3,1)$，$(2,3,2)$ 六种。 ### 评测数据规模 对于 $20$% 的评测数据，$1\leq b_i \leq 10^5$。 对于 $100$% 的评测数据，$1\leq n \leq 50$，$1\leq b_i \leq 10^9$。