Note that if $$$min(n, x+1) < k$$$, then the answer is $$$-1$$$.

Otherwise, there are two cases:

\begin{itemize} \item If $$$k=x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, \dots, k-1]$$$. \item If $$$k \ne x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, x, \dots, x]$$$. \end{itemize}

In both cases, we can construct the array and calculate its sum in linear time. The overall complexity is $$$O(n \cdot t)$$$.

Let's fix the color $$$x$$$ for which we will calculate the answer. If there is no $$$a_i = x$$$, then there will be no cells of color $$$x$$$, and the answer is $$$0$$$. Otherwise, there is at least one cell of color $$$x$$$.

To find the minimum rectangle containing all cells of this color, we need to find the topmost, bottommost, leftmost, and rightmost cells of this color in the array $$$b$$$. Let's find the prefix in $$$a$$$ of the maximum length, where all numbers are strictly less than $$$x$$$. Let the length of this prefix be $$$L$$$. Then in the first $$$L$$$ rows and columns of the array $$$b$$$, there will be no cells of color $$$x$$$, because for all these cells, the formula $$$b_{i, j} = min(a_i, a_j)$$$ will have a number from the prefix, and all numbers on it are less than $$$x$$$. In the $$$L+1$$$-th row and $$$L+1$$$-th column, there will be cells of color $$$x$$$, because $$$a_{L+1} \geq x$$$. Thus, we have found the topmost and leftmost cells of color $$$x$$$. To find the bottom and right cells, we need to find the longest suffix where all numbers are less than $$$x$$$.

Now we need to learn how to quickly find prefixes and suffixes for all colors. Notice that the prefix for color $$$x$$$ is not shorter than the prefix for color $$$x + 1$$$, so all prefixes can be calculated in just one pass through the array, similarly for suffixes.

Note that if there is a prefix for which there is a longer prefix that costs less, then it is useless to buy the shorter prefix. All its purchases can be replaced with purchases of the longer prefix, and the answer will only improve. Therefore, we can replace each $$$c_i$$$ with the minimum $$$c_j$$$ among $$$i \leq j \leq n$$$ (the minimum price of a prefix of length at least $$$i$$$). After this, we will have $$$c_i \leq c_{i+1}$$$.

Now let's solve the problem greedily. We want to maximize the first element of the resulting array. It will be equal to $$$k / c_1$$$, since we cannot buy more prefixes of length $$$1$$$ ($$$c_1$$$ is the smallest price). After buying $$$k / c_1$$$ prefixes of length $$$1$$$, we will have some coins left. Now we can replace some purchases of $$$c_1$$$ with purchases of longer prefixes to improve the answer.

How much will it cost to replace $$$c_1$$$ with $$$c_i$$$? It will cost $$$c_i - c_1$$$ coins. Moreover, note that to replace $$$c_1$$$ with $$$c_i$$$, we can sequentially replace $$$c_1$$$ with $$$c_2$$$, $$$c_2$$$ with $$$c_3$$$, $$$\ldots$$$, $$$c_{i-1}$$$ with $$$c_i$$$ (since $$$c_1 \leq c_2 \leq \ldots \leq c_i$$$). This means that we can make only replacements of purchases of $$$c_{i-1}$$$ with purchases of $$$c_i$$$.

Let's say we have maximized the first $$$i-1$$$ elements of the answer, and we have $$$x$$$ coins left. Now we want to replace some purchases of $$$c_{i-1}$$$ with $$$c_i$$$. How many replacements can we make? We can afford to make no more than $$$\frac{x}{c_i - c_{i-1}}$$$ replacements (if $$$c_{i-1} = c_i$$$, then we can replace all $$$c_{i-1}$$$), and we cannot replace more purchases than we have made, so no more than $$$a_{i-1}$$$ replacements (this is the number of purchases of $$$c_{i-1}$$$). Therefore, $$$a_i = \min(a_{i-1}, \frac{x}{c_i - c_{i-1}})$$$, as we want to maximize $$$a_i$$$. Finally, subtract the cost of replacements from the number of coins and move on to $$$c_{i+1}$$$.

Let's solve the problem using dynamic programming, let's store $$$dp[i][j]$$$ such that $$$dp[i][j]=1$$$ if it is possible to obtain an $$$XOR$$$ of $$$MEX$$$ values from the prefix up to $$$i$$$ (excluding $$$i$$$) equal to $$$x$$$, and $$$0$$$ otherwise. Notice that the answer cannot be greater than $$$n$$$. Therefore, the size of this two-dimensional array is $$$O(n^2)$$$.

Let's learn how to solve this in $$$O(n^3)$$$:

We iterate over $$$l$$$ from $$$1$$$ to $$$n$$$, and inside that, we iterate over $$$r$$$ from $$$l$$$ to $$$n$$$, maintaining the value $$$x=MEX([a_l, a_{l+1}, \dots, a_r])$$$. Then, for all $$$j$$$ from $$$0$$$ to $$$n$$$, we update $$$dp[r+1][j \oplus x]=1$$$ if $$$dp[l][j]=1$$$. This way, we update based on the case when the resulting set includes the set $$$[a_l, a_{l+1}, \dots, a_r]$$$.

We also need to update if $$$dp[l][x]=1$$$, we assign $$$dp[l+1][x]=1$$$. This accounts for the case when we do not include $$$a_l$$$ in the answer.

Let's define $$$MEX(l, r) = MEX([a_l, a_{l+1}, \dots, a_r])$$$, this will make the following text clearer.

Let's consider the segment $$$l, r$$$. Notice that if there exist $$$l_2$$$ and $$$r_2$$$ ($$$l \leq l_2 \leq r_2 \leq r$$$) such that $$$l_2 \ne l$$$ or $$$r_2 \ne r$$$ and $$$MEX(l, r)=MEX(l_2, r_2)$$$, then we can take the segment $$$l_2, r_2$$$ instead of the segment $$$l, r$$$ in the set of $$$MEX$$$ values, and the answer will remain the same. If, however, there is no such segment $$$l_2, r_2$$$ for the segment $$$l, r$$$, then we call this segment $$$l, r$$$ irreplaceable.

Now let's prove that there are no more than $$$n \cdot 2$$$ irreplaceable segments. For each irreplaceable segment, let's look at the larger element of the pair $$$a_l, a_r$$$, let's assume $$$a_l$$$ is larger (the other case is symmetric). Now, let's prove that there is at most one segment where $$$a_l$$$ is the left element and $$$a_l \leq a_r$$$, by contradiction:

Suppose there are at least 2 such segments, let's call their right boundaries $$$r_1, r_2$$$ ($$$r_1 < r_2$$$). Notice that $$$MEX(l, r_1) > a_l$$$, otherwise the segment $$$l, r_1$$$ would not be irreplaceable (we could remove $$$a_l$$$). Since $$$a_l >= a_{r_2}$$$, then $$$MEX(l, r) > a_{r_2}$$$. It is obvious that $$$a_{r_2}$$$ appears among the elements $$$[a_l, \dots, a_{r_1}]$$$, and therefore $$$MEX(l, r_2-1) = MEX(l, r_2)$$$, which means that the segment $$$l, r_2$$$ is not irreplaceable, contradiction.

For each $$$a_i$$$, there is at most one irreplaceable segment where it is the smaller of the two extremes, and at most one where it is the larger. Therefore, the total number of irreplaceable segments is no more than $$$2 \cdot n$$$.

Let's update the DP only through the irreplaceable segments, then the solution works in $$$O(n^2+n \cdot C)$$$ time, where $$$C$$$ is the number of irreplaceable segments. However, we have already proven that $$$C\leq 2n$$$, so the overall time complexity is $$$O(n^2)$$$.

Let's start by introducing a more convenient way to store numbers — an array $$$cnt$$$, where $$$cnt[x]$$$ represents the number of occurrences of $$$x$$$ in the prefix for which we are finding the answer. All $$$x$$$ such that $$$x > n$$$ will be added to $$$cnt[0]$$$ because applying the operation to $$${x}$$$ in such cases is optimal.

Let's introduce a few array operations that will be sufficient to solve the problem. \begin{itemize} \item Create the number $$$x$$$. Apply the operation to the set of numbers $$${0, 1, 2, \dots, x-1}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from the range $$$0$$$ to $$$x-1$$$ and adding $$$1$$$ to $$$cnt[x]$$$. \item Turn the number $$$x$$$ into $$$0$$$. To do this, apply the operation to $$${x}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from $$$cnt[x]$$$ and adding $$$1$$$ to $$$cnt[0]$$$. \item Create the number $$$x$$$ and clear the multiset. This is the same as creating the number $$$x$$$, but we apply the operation to all other numbers, leaving only the single number $$$x$$$ (or a larger number) in the set. \end{itemize}

It can be proven that by using only operations of this kind, we can always obtain the optimal answer.

Now we can forget about the original condition and solve the problem for the array.

Let's learn how to check if it is possible to create the number $$$k$$$ and clear the multiset:

First, let's try to create the number $$$k$$$. If it is possible, the answer is yes. Otherwise, we look at the rightmost number that is missing (or in other words, the rightmost $$$0$$$). We try to create it, and now we need to find the rightmost element $$$\leq 1$$$ to the left of it, and so on. To implement this, we need to maintain a number $$$p$$$ such that we subtract $$$p$$$ from all elements in the prefix (initially $$$p=1$$$), iterate through the array from right to left, and if $$$cnt[i]<p$$$, assign $$$p \mathrel{{+}{=}} (p-cnt[i])$$$. When we reach zero, $$$p$$$ may be greater than $$$cnt[0]$$$, in which case we need to use the operation to turn any number into $$$0$$$. To do this, simply check that the remaining number of elements in the array is greater than or equal to $$$p$$$.

This currently works in $$$O(k)$$$ time, which is not very efficient.

Optimization techniques:

First, let's maintain the sum of elements $$$sm$$$ and as soon as it becomes negative, terminate the process. To achieve this, when subtracting $$$p-cnt[i]$$$ from $$$p$$$, let's subtract $$$(p-cnt[i])\cdot(i-1)$$$ from $$$sm$$$. Now let's use a bottom-up segment tree to find the nearest number smaller than $$$p$$$ to the left in $$$O(\log(i))$$$ time.

Now let's notice that when we update through $$$cnt[i]$$$, we subtract at least $$$i-1$$$ from $$$sm$$$, so there can't be more than $$$O(\sqrt(n))$$$ different values of $$$i$$$ through which we will update.

Now we can answer for a specific $$$k$$$ in $$$O(\sqrt(n) \cdot \log(n))$$$ time, but in reality, the complexity is $$$O(\sqrt(n))$$$ (due to the peculiarities of the bottom-up segment tree), and the authors have a proof for this, but they are afraid that you will find an error in it, so they decided not to provide it(we will add proof later).

Now let's see how to solve the full problem:

Initially, the answer is $$$0$$$, and we notice that it does not decrease. So after each addition, we will check if it is possible to increase the answer and increase it as long as possible. The answer cannot exceed $$$n$$$, so we will perform no more than $$$2 \cdot n$$$ checks.

Overall, the solution works in $$$O(n \cdot \sqrt(n))$$$ time. That's how it is.

TBD

You can choose one best problem, or not choose if you think there is no such task.