Несправедлива шеренга
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) | Output (stdout) |
---|---|
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\), перестановка їх місцями не змінить вигляд шеренги.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|