Problem
Tom Sawyer ha convinto n dei suoi amici ad aiutarlo nel difficile compito di dipingere il recinto che circonda la casa di zia Polly. Il recinto è composto da k tavole consecutive, numerate da 1 a k, e dopo la k-esima tavola arriva di nuovo la prima.
Gli amici di Tom sono molto esigenti, l'i-esimo amico accetta di partecipare alla pittura solo se gli viene permesso di dipingere una sezione di tavole esattamente tutte consecutive. Tom ha un solo pennello, quindi i suoi amici dipingeranno a turno e subito l'intero segmento loro assegnato. L'unica cosa che resta da fare a Tom è scegliere l'ordine in cui invitare i suoi amici, nonché scegliere il numero desiderato di bacheche consecutive per ciascuno.
Allo stesso tempo, ciascuno degli amici di Tom è pronto a dipingere sia una tavola di recinzione non verniciata che una tavola che è già stata dipinta da uno dei suoi predecessori. Tuttavia, gli amici traggono più piacere dal dipingere una tavola non verniciata. Tom vuole scegliere un numero x e distribuire le sezioni di recinzione da dipingere in modo tale che ciascuno dei suoi amici dipinga almeno x assi non verniciate. Tom ama molto i suoi amici e vuole che ognuno di loro ottenga il massimo dal dipingere la recinzione, quindi cerca di massimizzare x.
Aiuta Tom a capire quanta gioia può portare ai suoi amici.
Formato dei dati di input
La prima riga del file di input contiene due numeri interi n (1 ≤ n ≤ 10
5 ) e k (1 ≤ k ≤ 10
9 ). La riga successiva contiene n numeri interi — valori a
i (1 ≤ a
i ≤ k).
Formato dei dati di output
Stampa un numero — valore massimo possibile di
x.
| Input |
Uscita |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Spiegazione
Nel primo esempio x = 5 perché uno degli amici non vuole dipingere più di cinque tavole. Verrà per primo, dipingerà i suoi cinque, dopodiché altre 10 tavole non verniciate andranno al secondo amico di Tom. Le restanti 85 tavole dovranno essere dipinte da Tom in persona.
Nel secondo esempio, x = 2 può essere raggiunto, ad esempio, in questo modo. Per prima cosa, il terzo amico dipinge le tavole da 4 a 6 (3 tavole non verniciate). Quindi il quarto amico dipinge le tavole da 1 a 5 (3 tavole non verniciate). Quindi il secondo amico dipinge le tavole da 1 a 8 (2 tavole non verniciate). Infine, il primo amico dipinge le tavole da 6 a 10 e da 1 a 2 (2 tavole non verniciate, si noti che la recinzione va in un ciclo e queste tavole formano un segmento consecutivo).