Muralhas reforçadas
Devido à sua localização privilegiada, com um relevo bem favorável, geralmente apenas muralhas frontais eram necessárias para a proteção de cidades medievais em Minas Gerais. Ainda hoje, é possível encontrar vestígios dessas construções ao admirar o belo horizonte da região.
Cada uma dessas muralhas era composta por um número de segmentos consecutivos, cada um com uma altura inicial medida em unidades, correspondendo ao número de blocos usados para construí-lo.
De tempos em tempos, os construtores reforçavam as muralhas escolhendo um segmento e empilhando blocos extras em um padrão de escada: o segmento escolhido recebia $K$ blocos adicionais, o anterior $K-1$, e assim sucessivamente até que apenas 1 bloco fosse adicionado ou que não houvesse mais segmentos à esquerda.
A solidez da defesa era determinada pela altura do segmento mais baixo da muralha.
Dada a descrição inicial de uma muralha, seu objetivo é determinar qual é a maior altura mínima possível após a aplicação de um único reforço.
Input
A primeira linha contém dois inteiros $N$ ($1 \leq N \leq 10^5$), o número de segmentos da muralha, e $K$ ($1 \leq K \leq N$), o número de blocos adicionados ao segmento escolhido.
A segunda linha contém $N$ inteiros $x_1, x_2, \dots, x_N$ ($1 \leq x_i \leq 10^9$), representando as alturas iniciais dos segmentos.
Output
Seu programa deve produzir uma única linha contendo um único inteiro: a maior altura mínima possível da muralha após um único reforço.
5 5 5 4 3 2 1
6
6 1 3 3 1 3 3 3
2
5 5 3 4 7 8 7
7
Explanation 3:
Se reforçarmos o primeiro segmento, a muralha passa a ter alturas $[8, 4, 7, 8, 7]$. O menor segmento nesse caso tem altura 4.
Reforçando o último segmento, temos $[4, 6, 10, 12, 12]$, e o menor valor é 4.
Entre todas as opções, a melhor escolha é reforçar o segundo segmento, obtendo $[7, 9, 7, 8, 7]$, cujo valor mínimo é 7.
Portanto, a maior altura mínima possível é 7.