Unfair Line

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

There are \(n\) students in the class. The height of the \(i\)-th student is \(h_i\).

During the defense class, they are lined up in a row. Let the height of the \(i\)-th student in the line be \(a_i\). Formally, the array \(a\) is some permutation of the array \(h\).

For the \(i\)-th student in the line, let us find the closest student \(j\) to the left such that \(a_j \ge a_i\). If no such student exists, we set \(l_i = \infty\), otherwise \(l_i = a_j\).

Similarly, let us find the closest student \(j\) to the right of the \(i\)-th student in the line such that \(a_j \ge a_i\). If no such student exists, we set \(r_i = \infty\), otherwise \(r_i = a_j\).

Zenyk believes that a student is in an unfair position if \(2 \cdot a_i \le l_i\) and \(2 \cdot a_i \le r_i\).

A line is considered unfair if every student is in an unfair position.

Calculate how many different-looking unfair lines can be formed from the students of the class, modulo the prime number \(10^9 + 7\).

Lines \(a\) and \(b\) look different if \(a_i \ne b_i\) for some \(i\).

Input

The first line contains an integer \(n\) — the number of students in the class.

The second line contains \(n\) integers \(h_i\) — the heights of the students in the class.

Output

Print an integer — the remainder of the answer divided by the prime number \(10^9 + 7\).

Constraints

\(1 \le n \le 10^5\),

\(1 \le h_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 1 2	1

Notes

In the example, only the line \(a = [1, 2, 1]\) satisfies the problem condition.

• There is no one to the left of the first student in the line, so \(l_1 = \infty\). To the right of him stands a taller student with a height of \(2\), so \(r_1 = 2\).

• The second student in the line is taller than all others, so \(l_2 = r_2 = \infty\).

• \(l_3 = 2, r_3 = \infty\).

For this line, all conditions \(2 \cdot a_1 \le l_1, 2 \cdot a_1 \le r_1, 2 \cdot a_2 \le l_2, 2 \cdot a_2 \le r_2, 2 \cdot a_3 \le l_3, 2 \cdot a_3 \le r_3\) are satisfied.

Note that even though two students have the same height of \(1\), swapping their places does not change the appearance of the line.