Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Након успешне експедиције, на Марсу је изграђен ,,Бибоп’’, први велики космодром у Сунчевом систему. Са њега сваког дана полеће \(N\) ракета, и за сваку ракету се зна њено планирано време полетања \(T_i\) (мерено у марсовским секундама протеклим од поноћи).
Када ракета треба да полети, у њу се утоварује терет који треба да понесе. Пошто радници на космодрому држе све кутије са теретом наслагане једну на другу, могу да утоваре само терет из кутије која је на врху гомиле. Срећом, веома су брзи – процес утоваривања не захтева нимало времена. Ако се деси да кутија коју траже није на врху, лансирање ракете мора да сачека док се не утоваре све кутије које су изнад тражене.
Да би олакшали овај процес лансирања, на космодрому постоји уређај који може да узме произвољан број кутија са врха гомиле и преврне их (тако да буду поређане супротним редоследом). Пошто је овај процес спор и може оштетити терет, уређај се може искористити само једном и то на почетку дана (пре првог полетања).
Радници ,,Бибопа’’ су грешком поређали кутије са теретом по редним бројевима ракета уместо по реду летења (тако да је на врху кутија намењена за ракету \(1\), испод ње за ракету \(2\), и тако даље). Помозите им да одаберу број кутија које ће окренути овим уређајем, тако да најдуже време које нека од ракета проведе чекајући на терет буде што мање.
У првом реду стандардног улаза налази се један природан број \(N\) – број ракета које полећу током дана. У другом реду стандардног улаза налази се \(N\) природних бројева, \(T_1, T_2, \dots, T_N\), где је \(i\)-ти број време полетања ракете са редним бројем \(i\).
У првом и једином реду стандардног излаза исписати један природан број, који представља минимално “најдуже време чекања”, које се достиже за оптималан избор преврнутих кутија.
5
6 3 8 2 553
2 2 10У првом примеру, прва ракета која треба да полети је ракета \(4\), две секунде после поноћи, али не може одмах да полети јер њен терет није на врху гомиле. Следећа по реду је ракета \(2\) (три секунде после поноћи), која такође мора да чека, а затим ракета \(5\), која исто чека.
Након што полети ракета \(1\) (шест секунди после поноћи), која не мора да чека на своју кутију, ракета \(2\) одмах може да полети, јер је њен терет сада на врху. Она је, дакле, чекала \(6-3=3\) секунде. Две секунде касније (осам секунди после поноћи) ракета \(3\) полеће без чекања, а одмах затим и ракете \(4\) и \(5\), са чекањима од \(6\) и \(3\) секунде редом.
Ако радници окрену горње четири кутије, тако да је редослед времена полетања ракета (од врха гомиле до дна) \(2,8,3,6,5\), ракета која полеће три секунде после поноћи ће чекати најдуже – пет секунди. Ниједан избор не даје чекања која су сва краћа од пет секунди, тако да је ово оптимално решење.
У другом примеру, ако се цела гомила преврне, ниједна ракета не мора да чека – пошто утоваривање терета не одузима време, ниједна ракета која полеће две секунде после поноћи не мора да чека.
Тест примери су подељени у три дисјунктне групе: * У тест примерима који вреде 20 поена важи \(1 \leq N \leq 100\). * У тест примерима који вреде 30 поена важи \(1 \leq N \leq 2000\). * У тест примерима који вреде 50 поена важи \(1 \leq N \leq 200000\).