Problema B - Aquele Onde Ninguém Imagina

Saiu há alguns dias, para tristeza de alguns fãs e alívio de outros, o último dos N episódios da famosíssima série "Onde Ninguém Imagina". No ONIb, o mais conhecido site de avaliações de séries e filmes, cada episódio recebeu uma nota A_i que é um inteiro positivo onde nenhuns dois episódios da série tiveram a mesma nota.

Parte I

O ONIb quer implementar uma funcionalidade que permite aos seus utilizadores, selecionando um dado episódio, descobrir a nota do melhor episódio que ainda assim foi pior do que o selecionado, entre os K anteriores e os K seguintes. Consegues escrever a lista das N avaliações que o site devia disponibilizar ao selecionar cada um dos N episódios?

Caso nenhum dos episódios anteriores ou seguintes seja pior que o selecionado, então a nota para esse caso será -1.

Exemplo

Vamos supor que N = 4, K = 2 e as notas obtidas foram A = (21, 73, 37, 258).

• Olhando para o primeiro elemento da lista, queremos procurar em {73,37} o maior número menor do que 21. Tal não existe, logo imprimimos -1.
• Olhando para o segundo, queremos procurar em {21,37,258} o maior número menor do que 73. Assim sendo, imprimimos 37.
• Continuamos o processo para os terceiro e quarto elementos e obtemos 21 e 73.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

O ONIb disponibiliza, para cada série, uma avaliação geral que é a mediana das avaliações das suas temporadas. A nota de cada temporada é nada mais nada menos que a mediana das notas dos episódios dessa temporada. Se o número de episódios de uma série for par, então a mediana é o máximo dos dois elementos medianos é a mediana da série.

Nota: A mediana de uma lista de números de tamanho ímpar é o número que é menor ou igual a metade dos números restantes e maior ou igual à outra metade. No caso de uma temporada ter tamanho par, dizemos que a sua mediana é o maior dos dois valores medianos.

Os criadores da série já há muito tinham afirmado que iam lançar K temporadas (sendo que K é sempre ímpar), mas nunca disseram onde começava e acabava cada uma. Consegues ajudá-los a organizar os episódios por temporadas de forma a maximizar a avaliação da série no ONIb?

Exemplo

Vamos supor que N = 5, K = 3 e as notas obtidas foram A = (21, 73, 37, 258, 38).

Se considerarmos a partição [21,73],[37], [258, 38] obtemos as notas por temporada de [73, 37, 258]. Como tal devemos imprimir a mediana das medianas, ou seja, a mediana de [73, 37, 258], que é 73. Esta é a melhor partição possível.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é o mesmo para as duas partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com dois inteiros separados por espaços N, representando o número de episódios, e K, o tamanho do intervalo na Parte I ou o número de séries na Parte II (que é sempre ímpar).

Segue-se uma linha com N inteiros separados por espaços, as notas de cada episódio.

Output

Parte I

O output deve conter uma só linha com N inteiros separados por espaços, as notas para cada episódio.

Parte II

O output deve conter uma só linha com um inteiro, a maior mediana de medianas.

Input do Exemplo 1

1
4 2
21 73 37 258

Output do Exemplo 1

-1 37 21 73

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
5 3
21 73 37 258 38

Output do Exemplo 2

73

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.