Solução escrita por João Pedro Castro
Conhecimento prévio necessário:
Primeiramente, vamos ver em que casos não existe uma resposta válida. Para chegar à um MEX de $$k$$ teremos que ter todos os $$k$$ números de $$0$$ até $$k – 1$$, e para isso ser realizado tanto $$n \geq k$$ (para termos espaço), quanto $$x \geq k – 1$$ (para que o limite não impeça que os coloquemos), se alguma dessas condições forem falsas podemos imprimir $$-1$$. Agora, depois de adicionar todos os números de $$0$$ até $$k – 1$$, de soma total: $$\frac{(k – 1)(k – 1 + 1)}{2} = \frac{k(k – 1)}{2}$$ (usando a Soma de Gauss), temos $$n – k$$ espaços restantes no array, e como só queremos a maior soma possível faz sentido colocar $$x$$ em todos os espaços restantes, já que ele é o maior número permitido; o único caso em que isso não pode ocorrer é quando $$k = x$$, e como $$k$$ não pode aparecer no array temos que colocar $$k – 1$$ (ou seja, tratar $$x := x – 1$$). Logo, a resposta final é $$\frac{k(k – 1)}{2} + x(n-k)$$. Tendo uma complexidade por teste de $$O(1)$$, logo uma complexidade total de $$O(t)$$, que passa tranquilamente.