CF2146E Yet Another MEX Problem

We define the weight of an array $ b $ consisting of $ m $ non-negative integers as the number of indices $ i $ ( $ 1\le i\le m $ ) satisfying $ b_i>\operatorname{mex}(b) $ . Here, $ \operatorname{mex}(b) $ denotes the minimum excluded (MEX) $ ^{\text{∗}} $ of the integers in $ b $ . You are given an array $ a $ consisting of $ n $ non-negative integers. For its subarray $ ^{\text{†}} $ $ [a_l, a_{l+1}, \ldots, a_r] $ , we denote the weight of the subarray as $ w(l,r) $ . For every $ 1\le i\le n $ , you have to find the maximum weight over all subarrays of $ a $ ending at index $ i $ . In other words, you have to find $ \max\limits_{1\le l\le i} w(l, i) $ for every $ 1\le i\le n $ . $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ b_1, b_2, \ldots, b_m $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ b $ . $ ^{\text{†}} $ An array $ c $ is a subarray of an array $ a $ if $ c $ 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.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n \le 3\cdot 10^5 $ ) — the length of $ a $ . The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0\le a_i\le n $ ) — the elements of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot 10^5 $ .

For each test case, output $ n $ integers, the $ i $ -th integer denoting the maximum weight over all subarrays of $ a $ ending at index $ i $ , i.e., $ \max\limits_{1\le l\le i}w(l,i) $ .

In the first test case, we have $ w(1, 1) = 0 $ , because $ \operatorname{mex}([a_1]) = 1 $ , and there are no indices satisfying $ a_i > 1 $ . In the second test case, we can calculate the weight of each subarray $ [l,r] $ by the definition: 1. $ w(1,1)=1 $ . Thus, $ \max\limits_{1\le l\le 1}w(l,1) =1 $ ; 2. $ w(1,2)=1 $ and $ w(2,2)=0 $ . Thus, $ \max\limits_{1\le l\le 2}w(l,2) =1 $ ; 3. $ w(1,3)=2 $ and $ w(2,3)=w(3,3)=1 $ . Thus, $ \max\limits_{1\le l\le 3}w(l,3) =2 $ ; 4. $ w(1,4)=2 $ , $ w(2,4)=w(3,4)=1 $ , and $ w(4,4)=0 $ . Thus, $ \max\limits_{1\le l\le 4}w(l,4) =2 $ ; 5. $ w(1,5)=0 $ , $ w(2,5)=w(3,5)=1 $ , and $ w(4,5)=0,w(5,5)=1 $ . Thus, $ \max\limits_{1\le l\le 5}w(l,5) =1 $ . For example, $ w(1, 4) = 2 $ because $ \operatorname{mex}([a_1, a_2, a_3, a_4]) = 1 $ , and there are two indices satisfying $ a_i>1 $ in the subarray: $ 1 $ and $ 3 $ .