Subarray Minimum Operation Permutations

Given a permutation $h=[h_1, h_2,\dots, h_n]$ of length $n$, you are allowed to perform the following operation any number of times (possibly zero): choose an interval $[l,r]$ ($1\le l\le r\le n$) and update every element in that interval to the minimum value in that interval, i.e., for each $i\in [l,r]$, set $$h_i=\min_{j=l}^r h_j.$$

After performing some operations, some arrays (configurations) might be obtained. Determine the number of distinct arrays that can be obtained. Output the answer modulo $10^9+7$.

Observation: It can be shown that any sequence of operations essentially chooses, for each adjacent pair, whether to merge them into the same block (by propagating the minimum) or not. Consequently, the answer is exactly $$2^{n-1}\pmod{10^9+7}.$$

inputFormat

The first line contains an integer $n$ $(1 \le n \le 10^5)$, the length of the permutation.

The second line contains $n$ distinct integers $h_1, h_2, \dots, h_n$ separated by spaces, representing a permutation of the numbers from $1$ to $n$.

outputFormat

Print a single integer, the number of distinct arrays obtainable by performing the operation any number of times, modulo $10^9+7$.

sample

1
1

1