CF2117H Incessant Rain

Note the unusual memory limit. Silver Wolf gives you an array $ a $ of length $ n $ and $ q $ queries. In each query, she replaces an element in $ a $ . After each query, she asks you to output the maximum integer $ k $ such that there exists an integer $ x $ such that it is the $ k $ -majority of a subarray $ ^{\text{∗}} $ of $ a $ . An integer $ y $ is the $ k $ -majority of array $ b $ if $ y $ appears at least $ \lfloor \frac{|b|+1}{2} \rfloor +k $ times in $ b $ , where $ |b| $ represents the length of $ b $ . Note that $ b $ may not necessarily have a $ k $ -majority. $ ^{\text{∗}} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ q $ ( $ 1 \leq n, q \leq 3 \cdot 10^5 $ ) — the length of $ a $ and the number of queries. The following line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ). The following $ q $ lines contain two integers $ i $ and $ x $ , denoting the query that replaces $ a_i $ with $ x $ ( $ 1 \leq i, x \leq n $ ). It is guaranteed that the sum of $ n $ and the sum of $ q $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output the answer to all queries on a single new line, separated by a space.