Несправедлива шеренга

Limits: 2 sec., 256 MiB

У класі є $n$ учнів. Зріст $i$-ого учня — $h_i$.

На уроці захисту Вітчизни їх вишикують у шеренгу. Нехай зріст $i$-ого учня в шерензі — $a_i$. Формально масив $a$ — це деяка перестановка масиву $h$.

Для $i$-ого учня в шерензі знайдемо найближчого зліва учня $j$ такого, що $a_j \ge a_i$. Якщо такого учня не існує, то покладемо $l_i = \infty$, інакше $l_i = a_j$.

Аналогічно, знайдемо для $i$-ого учня в шерензі знайдемо найближчого справа учня $j$ такого, що $a_j \ge a_i$. Якщо такого учня не існує, то покладемо $r_i = \infty$, інакше $r_i = a_j$.

Зеник вважає, що учень стоїть на несправедливому місці, якщо $2 \cdot a_i \le l_i$ та $2 \cdot a_i \le r_i$.

Шеренга вважається несправедливою, якщо кожен учень стоїть на несправедливому місці.

Порахуйте, скільки несправедливих шеренг, що мають різний вигляд, можна утворити з учнів класу за модулем простого числа $10^9 + 7$.

Шеренги $a$ і $b$ мають різний вигляд, якщо $a_i \ne b_i$ для деякого $i$.

Input

У першому рядку задано ціле число $n$ — кількість учнів у класі.

У другому рядку задано $n$ цілих чисел $h_i$ — зрости учнів класу.

Output

Виведіть ціле число — остачу від ділення відповіді на просте число $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

У прикладі умову задачі задовольняє тільки шеренга $a = [1, 2, 1]$.

• Від першого учня в шерензі не стоїть ніхто зліва, тому $l_1 = \infty$. Праворуч від нього стоїть вищий учень зі зростом $2$, тому $r_1 = 2$.

• Другий учень у шерензі є вищим за всіх інших, тому $l_2 = r_2 = \infty$.

• $l_3 = 2, r_3 = \infty$.

Для цієї шеренги виконуються всі умови $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$.

Зауважте, що хоч і два учні мають однаковий зріст $1$, перестановка їх місцями не змінить вигляд шеренги.