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

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\), перестановка їх місцями не змінить вигляд шеренги.