Uzb Eng

C8H. DEVORNI BOYASH
: 2 c
: 64

Tom ozining n ta dostini Pol xolasini uyini orab turgan devorni boyash uchun yordamga kondirdi. Devor 1 dan k gacha raqamlangan k ta ketma-ket taxtalardan tashkil topgan. K-taxtadan keyin yana birinchi taxta boshlanadi.
Tomni doslari judayam injiq. I-dosti faqatgina ketma-ket keluvchi ai ta taxtani boyashga rozi, qolgan ketma-ketlikni boyamaydi.
Tomni chotkasi bitta. Shuning uchun uning dostrlari unga berilgan barcha oraliqni toliq va navbat bilan boyaydi. Tomga faqat tartibni hamda xoxishga kora ketma-ketlikni aniqlash qoldi.
Shuning uchun Tomni har bir dosti devorning boyalmagan sohasini va oldin boyalgan sohani boyashga ham tayyor.
Tom shunday x sonini tanlashi kerak va devorni shunday bolishi kerakki, bunda har bir dosti kamida x ta boyalmagan taxtani boyasin. Tom dostlarini yaxshi koradi va u boyash jarayonidan doatlarini maksimal darajada rohat olishlarini xoxlaydi. Shuning uchun u x ni kattalashtirishga harakat qiladi. Tomga dostlari x qanday bolganda xursand bolishlariga yordam bering.

:
Birinchi satrda ikkita n ( 1 ≤ n ≤ 105) va k (1 ≤ k ≤ 109) sonlari berilgan. Keyingi satrda n ta ai (1 ≤ ai ≤ k) sonlari berilgan.

:
Mumkin bolgan x ning eng katta qiymaytini chiqaring.

2 100
5 10
4 10
7 8 3 5
1 1
1
10 10
1 2 3 4 5 6 7 8 9 10
5


2


1


1
: Geometriya
: acm.tuit.uz 8-contest


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.