시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB26181785.000%

문제

http://vip.latnet.lv/lio/ARHIVS/LIO04/ino17kopa.pdfaAdomas, besiruošdamas žiemai, nusipirko N malkų. Visos malkos yra vienodo skersmens, tačiau jos gali būti skirtingo ilgio. Adomas nori sukrauti visas malkas savo rūsyje.

Adomas malkas krauna tokiu būdu:

  1. Ant grindų paguldoma pirma malka.
  2. Ant viršaus paguldoma kuo daugiau malkų, statmenai pirmajai. Ant L ilgio malkos galima sukrauti daugiausiai L kitų malkų.
  3. Tuomet ant viršaus vėl guldoma viena malka, statmenai po ja esančioms. Ji turi būti ne ilgesnė negu po ja esančių malkų skaičius.
  4. Ant viršaus vėl paguldoma kuo daugiau malkų, statmenai. Ir taip toliau.

1 pav. Malkų krūvos pavyzdys.

Adomas nėra labai aukštas. Tad jis nori, kad malkų krūva būtų kuo žemesnė.

Jums žinomi visų malkų ilgiai. Raskite, koks yra mažiausias įmanomas malkų krūvos aukštis, jas kraunant nurodytu būdu.

입력

Pirmoje eilutėje įrašytas malkų skaičius N. Antroje eilutėje pateikiama N tarpais atskirtų sveikųjų skaičių Li, žyminčių malkų ilgius.

출력

Išveskite vienintelį skaičių – mažiausią įmanomą malkų krūvos aukštį.

제한

  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ Li ≤ 1 000 000 (1 ≤ i ≤ N)

서브태스크

번호배점제한
120

Visų malkų ilgiai vienodi

225

Li ≤ 2

330

N ≤ 1 000

425

Papildomų ribojimų nėra

예제 입력 1

5
1 1 2 1 1

예제 출력 1

4

예제 입력 2

8
2 2 5 3 1 2 7 3

예제 출력 2

2

채점 및 기타 정보

  • 예제는 채점하지 않는다.