Задание 8. Запросы на отрезках (RSQ/RMQ)

8.1 Префиксные суммы

Дана последовательность чисел $A = [a_1, a_2, ..., a_n]$ . Нужно найти сумму $S(i,j)$ чисел на отрезке от $i$ до $j$ включительно: $S(i,j) = \sum_{k=i}^{j}{a_k}$ .

Используйте алгоритм префиксных сумм. Трудоемоксть вычисления суммы должна быть $O(1)$ .

Вход

В первой строке число $N$ ( $1 \le N \le 10^5$ ) — количество элементов в массиве $A$ . В следующей строке записано $N$ чисел через пробел — элементы $a_i$ ( $-128 \le a_i < 127$ ) массива $A$ . В следующих $K$ ( $1 \le K \le 10^7$ ) строках идут запросы: числа $i$ и $j$ , чтобы вычислить сумму $S(i,j)$ .

Выход

$K$ строк, в каждой их которых одно число — результат вычисления суммы на отрезке $S(i,j)$ .

Пример

Вход

10
1 4 3 -6 2 6 -8 2 3 5
0 9
2 4
3 7
4 4

Выход

8.2 Дерево отрезков для минимумов

Дана последовательность чисел $A = [a_1, a_2, ..., a_n]$ . Нужно найти минимум $M(i,j)$ чисел на отрезке от $i$ до $j$ : $M(i,j) = \min_{i \le k < j}{a_k}$ .

Используйте структуру данных дерево отрезков. Поиск минимума должен быть $O(log(n))$

Вход

В первой строке число $N$ ( $1 \le N \le 10^5$ ) — количество элементов в массиве $A$ . В следующей строке записано $N$ чисел через пробел — элементы $a_i$ ( $-10^7 \le a_i \le 10^7$ ) массива $A$ . В следующих $K$ ( $1 \le K \le 10^7$ ) строках идут запросы: числа $i$ и $j$ , чтобы вычислить минимум $M(i,j)$ .

Выход

$K$ строк, в каждой их которых одно число — результат вычисления минимума на отрезке $M(i,j)$ .

Пример

Вход

10
1 4 3 -6 2 6 -8 2 3 5
0 9
2 4
4 5
0 3
7 10

Выход