B. Index and Maximum Value
data structures; greedy
After receiving yet another integer array \(a_1, a_2, \ldots, a_n\) at her birthday party, Index decides to perform some operations on it.Formally, there are \(m\) operations that she is going to perform in order. Each of them belongs to one of the two types: \(\texttt{+ l r}\). Given two integers \(l\) and \(r\), for all \(1 \leq i \leq n\) such that \(l \leq a_i \leq r\), set \(a_i := a_i + 1\). \(\texttt{- l r}\). Given two integers \(l\) and \(r\), for all \(1 \leq i \leq n\) such that \(l \leq a_i \leq r\), set \(a_i := a_i - 1\). For example, if the initial array \(a = [7, 1, 3, 4, 3]\), after performing the operation \(\texttt{+} \space 2 \space 4\), the array \(a = [7, 1, 4, 5, 4]\). Then, after performing the operation \(\texttt{-} \space 1 \space 10\), the array \(a = [6, 0, 3, 4, 3]\).Index is curious about the maximum value in the array \(a\). Please help her find it after each of the \(m\) operations.
Each test consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \leq t \leq 2 \cdot 10^4\)) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\)) — the length of the array and the number of operations.The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — the initial array \(a\).Then \(m\) lines follow, each line corresponds to the operation, in the following format: \(\texttt{c l r}\) (\(c \in \{\texttt +, \texttt -\}\), \(l\) and \(r\) are integers, \(1 \leq l \leq r \leq 10^9\)) — the description of the operation.Note that the elements \(a_i\) may not satisfy \(1\le a_i\le 10^9\) after some operations, as it is shown in the example.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\), and the sum of \(m\) over all test cases does not exceed \(10^5\).
For each test case, output one single line containing \(m\) integers, with the \(i\)-th of them describing the maximum value of the array after the \(i\)-th operation.
In the first test case, the process of the operations is listed below: After the first operation, the array becomes equal \([2,3,4,3,2]\). The maximum value is \(4\). After the second operation, the array becomes equal \([1,2,4,2,1]\). The maximum value is \(4\). After the third operation, the array becomes equal \([2,3,4,3,2]\). The maximum value is \(4\). After the fourth operation, the array becomes equal \([3,4,5,4,3]\). The maximum value is \(5\). After the fifth operation, the array becomes equal \([3,4,5,4,3]\). The maximum value is \(5\).In the second test case, the process of the operations is listed below: After the first operation, the array becomes equal \([2,4,4,5,5]\). The maximum value is \(5\). After the second operation, the array becomes equal \([3,4,4,5,5]\). The maximum value is \(5\). After the third operation, the array becomes equal \([3,3,3,4,4]\). The maximum value is \(4\). After the fourth operation, the array becomes equal \([2,2,2,4,4]\). The maximum value is \(4\). After the fifth operation, the array becomes equal \([1,1,1,3,3]\). The maximum value is \(3\).