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.