CF2084G2 Wish Upon a Satellite (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $ t \le 10^4 $ , $ n \le 5 \cdot 10^5 $ and the sum of $ n $ does not exceed $ 5 \cdot 10^5 $ . You can hack only if you solved all versions of this problem. For a non-empty sequence $ c $ of length $ k $ , define $ f(c) $ as follows: - Turtle and Piggy are playing a game on a sequence. They are given the sequence $ c_1, c_2, \ldots, c_k $ , and Turtle goes first. Turtle and Piggy alternate in turns (so, Turtle does the first turn, Piggy does the second, Turtle does the third, etc.). - The game goes as follows: - Let the current length of the sequence be $ m $ . If $ m = 1 $ , the game ends. - If the game does not end and it's Turtle's turn, then Turtle must choose an integer $ i $ such that $ 1 \le i \le m - 1 $ , set $ c_i $ to $ \min(c_i, c_{i + 1}) $ , and remove $ c_{i + 1} $ . - If the game does not end and it's Piggy's turn, then Piggy must choose an integer $ i $ such that $ 1 \le i \le m - 1 $ , set $ c_i $ to $ \max(c_i, c_{i + 1}) $ , and remove $ c_{i + 1} $ . - Turtle wants to maximize the value of $ c_1 $ in the end, while Piggy wants to minimize the value of $ c_1 $ in the end. - $ f(c) $ is the value of $ c_1 $ in the end if both players play optimally. For a permutation $ p $ of length $ n $ $ ^{\text{∗}} $ , Turtle defines the beauty of the permutation as $ \sum\limits_{i = 1}^n \sum\limits_{j = i}^n f([p_i, p_{i + 1}, \ldots, p_j]) $ (i.e., the sum of $ f(c) $ where $ c $ is a non-empty subsegment $ ^{\text{†}} $ of $ p $ ). Piggy gives Turtle a permutation $ a $ of length $ n $ where some elements are missing and represented by $ 0 $ . Turtle asks you to determine a permutation $ b $ of length $ n $ such that: - $ b $ can be formed by filling in the missing elements of $ a $ (i.e., for all $ 1 \le i \le n $ , if $ a_i \ne 0 $ , then $ b_i = a_i $ ). - The beauty of the permutation $ b $ is maximized. For convenience, you only need to find the maximum beauty of such permutation $ b $ . $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^{\text{†}} $ A sequence $ a $ is a subsegment of a sequence $ b $ if $ a $ can be obtained from $ b $ 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 5 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ). It is guaranteed that the elements of $ a $ that are not $ 0 $ are distinct. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

For each test case, output a single integer — the maximum beauty of the permutation $ b $ .

In the first test case, the permutation $ b $ with the maximum beauty is $ [1, 2] $ . The beauty of $ [1, 2] $ is $ 4 $ since $ f([1]) + f([2]) + f([1, 2]) = 1 + 2 + 1 = 4 $ . If $ c = [1, 2] $ , then $ f(c) = 1 $ since Turtle can only choose $ i = 1 $ and he will set $ c_1 $ to $ \min(c_1, c_2) = 1 $ . In the second test case, one of the permutations $ b $ with the maximum beauty is $ [3, 2, 1] $ . The beauty of $ [3, 2, 1] $ is $ 12 $ since $ f([3]) + f([2]) + f([1]) + f([3, 2]) + f([2, 1]) + f([3, 2, 1]) = 3 + 2 + 1 + 2 + 1 + 3 = 12 $ . In the third test case, one of the permutations $ b $ with the maximum beauty is $ [2, 1, 3] $ . In the fourth test case, if $ c = [3, 2, 4, 5, 1] $ , then $ f(c) = 3 $ . One of the possible game processes is as follows: - Turtle can choose $ i = 3 $ . Then he will set $ c_3 $ to $ \min(c_3, c_4) = 4 $ and remove $ c_4 $ . The sequence $ c $ will become $ [3, 2, 4, 1] $ . - Piggy can choose $ i = 1 $ . Then he will set $ c_1 $ to $ \max(c_1, c_2) = 3 $ and remove $ c_2 $ . The sequence $ c $ will become $ [3, 4, 1] $ . - Turtle can choose $ i = 2 $ . Then he will set $ c_2 $ to $ \min(c_2, c_3) = 1 $ and remove $ c_3 $ . The sequence $ c $ will become $ [3, 1] $ . - Piggy can choose $ i = 1 $ . Then he will set $ c_1 $ to $ \max(c_1, c_2) = 3 $ and remove $ c_2 $ . The sequence $ c $ will become $ [3] $ . - The length of the sequence becomes $ 1 $ , so the game will end. The value of $ c_1 $ will be $ 3 $ in the end. In the fifth test case, one of the permutations $ b $ with the maximum beauty is $ [1, 3, 2, 5, 6, 4, 7] $ .