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}). 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.