Problem Description

A sequence $ B $ is defined as a "zigzag sequence" if it satisfies one of the following two conditions, where $ |B| $ represents the number of elements in $ B $.

• It has a length of 2 or more, and for all $i\ (1\ \leq\ i\ \lt\ |B|)$, the following holds:
• If $ i $ is odd, then $B_i\ \lt\ B_{i+1}$
• If $ i $ is even, then $B_i\ \gt\ B_{i+1}$
• It has a length of 2 or more, and for all $i\ (1\ \leq\ i\ \lt\ |B|)$, the following holds:
• If $ i $ is odd, then $B_i\ \gt\ B_{i+1}$
• If $ i $ is even, then $B_i\ \lt\ B_{i+1}$

You are given a sequence $ A $ of length $ N $. There are $ 2^N-1 $ non-empty (not necessarily contiguous) subsequences of $ A $. How many of these subsequences are zigzag sequences?
Output the count modulo $ (10^9+7) $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $

Output Format

Output the number of non-empty subsequences of $ A $ that are zigzag sequences, modulo $ (10^9+7) $.

Sample Input and Output

Sample Input #1

3
1 3 2

Sample Output #1

4

Sample Input #2

3
1 3 3

Sample Output #2

2

Sample Input #3

4
2 2 2 2

Sample Output #3

0

Sample Input #4

6
83 65 79 54 88 69

Sample Output #4

44

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• All inputs are integers.

Sample Explanation 1

The non-empty subsequences of $ A $ are as follows. Among them, the ones marked with an asterisk are zigzag sequences.
- $ (1) $
- $ (3) $
- $ (2) $
- $ (1,3) $ $\cdots$ ☆
- $ (1,2) $ $\cdots$ ☆
- $ (3,2) $ $\cdots$ ☆
- $ (1,3,2) $ $\cdots$ ☆

Sample Explanation 2

Note that two subsequences are considered different if they are extracted from different positions, even if they are the same as sequences. In this case, the subsequences of $ A $ that are also zigzag sequences are $ (1,3) $ and $ (1,3) $.

Sample Explanation 3

The answer can be $ 0 $.

见题面 Input 部分

见题面 Output 部分