Tteokguk

Do you know Naver D2? D2 stands for For Developers, By Developers, a Naver developer support program that developers build themselves for developers. It shares the technology and knowledge Naver has accumulated, supports outside developers to strengthen Korean developers' capabilities, and through this aims to create a virtuous cycle in which the whole industry and Naver grow together.

Naver's developer support has in fact continued steadily for a long time. There have been many support programs, including the developer conference DEVIEW, releases of open source and development tools, and support for academic societies and communities. Naver D2 is what integrated these various programs into one.

NAVER D2, a developer support program that grows together, holds the developer conference DEVIEW every year.

In 2021 the preparation of talks for DEVIEW, to present a variety of topics, is in full swing. But a very big problem has come up. So many empty tteokguk bowls left over from meals have piled up on the desk that the work cannot proceed. You happened to be passing by and decided to help!

On top of a tteokguk bowl you can stack one tteokguk bowl of a smaller size. On top of the stacked tteokguk bowl you can stack another tteokguk bowl in the same way. For example, for tteokguk bowls of sizes $4$, $2$, $3$, $1$, you can stack them in the order $4-3-2-1$, but you cannot stack them in the order $3-4-2-1$. One or more tteokguk bowls stacked this way are called a tteokguk bowl tower.

You want to make the number of tteokguk bowl towers as small as possible to free up space on the desk.

The following are examples of the number of tteokguk bowl towers you can make from tteokguk bowls of sizes $4$, $2$, $3$, $1$, $2$, and the minimum number is $2$.

• $5$ : $[4,\,2,\,3,\,1,\,2]$
• $4$ : $[4-2,\,3,\,1,\,2]$ or $[4-3,\,2,\,1,\,2]$ or $[4,\,3-2,\,1,\,2]$ or $\cdots$
• $3$ : $[4-2,\,3-1,\,2]$ or $[4-1,\,3-2,\,2]$ or $[4-3,\,2-1,\,2]$ or $\cdots$
• $2$ : $[4-2,\,3-2-1]$ or $[4-2-1,\,3-2]$ or $[4-3-2,\,2-1]$ or $\cdots$
• It cannot be made into $1$ tteokguk bowl tower.

Given the sizes of the tteokguk bowls, find the minimum number of tteokguk bowl towers. As a token of thanks, NAVER D2 will accept one problem of SUAPC 2021w as correct for you.

The input is given as follows.

$N$

$c_1 \ c_2 \ ... \ c_N$

Print the minimum number of tteokguk bowl towers.

• $N$ is the number of tteokguk bowls. ($1 \le N \le 500\,000$)
• $c_i$ is the size of the $i$-th tteokguk bowl. ($1 \le c_i \le 50\,000$)
• All numbers in the input are integers.