Получив на свой день рождения ещё один массив целых чисел \(a_1, a_2, \ldots, a_n\), Индекс решает выполнить некоторые операции над ним.
Формально, она собирается выполнить \(m\) операций по порядку. Каждая из них относится к одному из двух типов:
- \(\texttt{+ l r}\). Даны два целых числа \(l\) и \(r\), для всех \(1 \leq i \leq n\), таких что \(l \leq a_i \leq r\), присвоить \(a_i := a_i + 1\).
- \(\texttt{- l r}\). Даны два целых числа \(l\) и \(r\), для всех \(1 \leq i \leq n\), таких что \(l \leq a_i \leq r\), присвоить \(a_i := a_i - 1\).
Например, если начальный массив \(a = [7, 1, 3, 4, 3]\), после выполнения операции \(\texttt{+} \space 2 \space 4\), массив \(a = [7, 1, 4, 5, 4]\). Затем, после выполнения операции \(\texttt{-} \space 1 \space 10\), массив \(a = [6, 0, 3, 4, 3]\).
Индекс интересует максимальное значение в массиве \(a\). Пожалуйста, помогите ей найти его после каждой из \(m\) операций.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую \(m\) целых чисел, где \(i\)-е из них описывает максимальное значение массива после \(i\)-й операции.
Примечание
В первом наборе входных данных процесс операций представлен ниже:
- После первой операции массив становится равным \([2,3,4,3,2]\). Максимальное значение \(4\).
- После второй операции массив становится равным \([1,2,4,2,1]\). Максимальное значение \(4\).
- После третьей операции массив становится равным \([2,3,4,3,2]\). Максимальное значение \(4\).
- После четвёртой операции массив становится равным \([3,4,5,4,3]\). Максимальное значение \(5\).
- После пятой операции массив становится равным \([3,4,5,4,3]\). Максимальное значение \(5\).
Во втором наборе входных данных процесс операций представлен ниже:
- После первой операции массив становится равным \([2,4,4,5,5]\). Максимальное значение \(5\).
- После второй операции массив становится равным \([3,4,4,5,5]\). Максимальное значение \(5\).
- После третьей операции массив становится равным \([3,3,3,4,4]\). Максимальное значение \(4\).
- После четвёртой операции массив становится равным \([2,2,2,4,4]\). Максимальное значение \(4\).
- После пятой операции массив становится равным \([1,1,1,3,3]\). Максимальное значение \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 5
1 2 3 2 1
+ 1 3
- 2 3
+ 1 2
+ 2 4
- 6 8
5 5
1 3 3 4 5
+ 1 4
+ 2 3
- 4 5
- 3 3
- 2 6
5 5
1 1 1 1 1
+ 2 3
- 4 5
+ 1 6
- 2 5
+ 1 8
1 1
1
- 1 1
1 1
1000000000
+ 1000000000 1000000000
|
4 4 4 5 5
5 5 4 4 3
1 1 2 1 2
0
1000000001
|