P8330 [ZJOI2022] Mode

Kurenai Kujou is a pitiful girl with superpowers, but her superpower can only be used on some strange things. One day, Kurenai got a sequence $a_1, a_2, \ldots, a_n$. She can use her superpower on this sequence once: choose an interval $[l, r]$ ($1 \le l \le r \le n$) and an integer $k \in [-{10}^9, {10}^9]$, and add $k$ to all numbers $a_l, a_{l + 1}, \ldots, a_r$ in the interval. Kurenai likes sequences that look as consistent as possible, so she wants the final sequence to have the mode occur as many times as possible. Given the sequence $a$, you need to output the maximum possible number of occurrences of the mode in the final sequence, and output all possible values of this mode. Note that for a sequence, the mode may have more than one value.

The input contains multiple test cases. The first line contains the number of test cases $T$. For each test case, the first line contains the sequence length $n$, and the second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

For each test case, output the maximum possible number of occurrences of the mode in the final sequence on the first line. Suppose this mode has $k$ different possible values. Then output these values in increasing order, one per line, for a total of $k$ lines.

For all testdata: $1 \le T \le 20$, $2 \le n \le 2 \times {10}^5$, $1 \le a_i \le {10}^9$, it is guaranteed that $\sum n \le 5 \times {10}^5$, and the $a_i$ are not all equal. The specific limits for each test point are shown in the table below: | Test Point ID | $\sum n \le$ | $n \le$ | Special Constraint | |:-:|:-:|:-:|:-:| | $1 \sim 4$ | $3000$ | $300$ | None | | $5 \sim 8$ | $5 \times {10}^5$ | $2 \times {10}^5$ | $a_i$ has only $5$ distinct values | | $9 \sim 10$ | $2 \times {10}^5$ | $50000$ | None | | $11 \sim 20$ | $5 \times {10}^5$ | $2 \times {10}^5$ | None | Translated by ChatGPT 5