CF2002E Cosmic Rays

Given an array of integers $ s_1, s_2, \ldots, s_l $ , every second, cosmic rays will cause all $ s_i $ such that $ i=1 $ or $ s_i\neq s_{i-1} $ to be deleted simultaneously, and the remaining parts will be concatenated together in order to form the new array $ s_1, s_2, \ldots, s_{l'} $ . Define the strength of an array as the number of seconds it takes to become empty. You are given an array of integers compressed in the form of $ n $ pairs that describe the array left to right. Each pair $ (a_i,b_i) $ represents $ a_i $ copies of $ b_i $ , i.e. $ \underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ times}} $ . For each $ i=1,2,\dots,n $ , please find the strength of the sequence described by the first $ i $ pairs.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le3\cdot10^5 $ ) — the length of sequence $ a $ . The next $ n $ lines contain two integers each $ a_i $ , $ b_i $ ( $ 1\le a_i\le10^9,0\le b_i\le n $ ) — the pairs which describe the sequence. It is guaranteed that the sum of all $ n $ does not exceed $ 3\cdot10^5 $ . It is guaranteed that for all $ 1\le i

For each test case, print one line containing $ n $ integers — the answer for each prefix of pairs.

In the first test case, for the prefix of length $ 4 $ , the changes will be $ [0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[] $ , so the array becomes empty after $ 5 $ seconds. In the second test case, for the prefix of length $ 4 $ , the changes will be $ [6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[] $ , so the array becomes empty after $ 7 $ seconds.