Considerada uma das atrações naturais mais belas do mundo, as Cataratas do Iguaçu é um grande e belo complexo de cachoeiras localizado em Foz do Iguaçu, Brasil. As Cataratas são tão lindas que atraem milhares de turistas todos os anos. O Sr. Lion é um destes turistas que planeja visitar as Cataratas na próxima temporada.

Considere que a temporada tem N dias, numerados de 1 a N. Depois de analisar a previsão do tempo na região durante a temporada, o sr. Lion sabe que, no dia i, a vazão das Cataratas será de $W_i$ litros por segundo (l/s). O sr. Lion decidiu visitar a atração durante K dias consecutivos, isto é, ele irá escolher um inteiro i entre 1 e $N-K+1$ (inclusive) e visitar as Cataratas nos dias $i,i+1,...,i+K-1$.

Entretanto, para aproveitar as Cataratas o máximo possível, ele deseja que sua viagem seja a mais balanceada possível. O balanceamento visual de uma sequência de dias $i,...,i+K- 1$ é definido como o inteiro B tal que:

A vazão das Cataratas em algum dos dias na sequência é exatamente B l/s;
A vazão em metade dos outros $K-1$ dias deve ser menor ou igual a B l/s;
A vazão na outra metade dos outros $K-1$ dias deve ser maior ou igual a B l/s;
Ajude o sr. Lion a decidir em quais dias ele deve visitar as Cataratas de tal forma que o balanceamento visual seja o maior possível.

Entrada

A primeira linha contém os inteiros N e K ($1 \le K \le N \le 2*10^5$, K é ímpar). A segunda linha contém os inteiros $W_1,W_2,...,W_N,$ ($0 \le W_i \le 10^6$ para todo $1 \le i \le N$), a vazão em cada dia da temporada, em litros por segundo.

Saída

Imprima uma linha contendo o balanceamento visual máximo que o sr. Lion pode obter.