Вам задана перестановка \(p_1, p_2, \dots, p_n\). Вам необходимо ответить на \(q\) запросов. Каждый запрос представляет из себя пару \((l_i, r_i)\) и Вам необходимо посчитать \(f(l_i, r_i)\).
Пусть \(m_{l, r}\) — это позиция максимума в подотрезке \(p_l, p_{l+1}, \dots, p_r\).
Тогда, \(f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r)\) если \(l \le r\) либо \(0\) в противном случае.
Выходные данные
Выведите \(q\) целых чисел — значения \(f(l_i, r_i)\) для соответствующих запросов.
Примечание
Разбор запросов:
- \(f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1\);
- \(f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6\);
- \(f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8\);
- \(f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5\);
- \(f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
3 1 4 2
2 1 1 2 1
2 3 4 4 1
|
1 6 8 5 1
|