33886번 - 카드 뭉치

문제

앞면에 양의 정수가 적혀 있는 $N$장의 카드 뭉치가 있다. 처음에 카드는 앞면이 위로 보이도록 일렬로 나열되어 있고, 왼쪽에서 $i$번째 카드에 적혀있는 정수는 $A_i$이다.

여러분은 아래의 규칙에 따라 카드 뭉치를 나눠 여러 개의 카드 뭉치로 만들어야 한다.

• 카드 뭉치를 나눌 때는 연속된 구간 단위로 분할하여 나눠야 한다.
• 카드 뭉치 내 카드의 순서는 바꿀 수 없다.
• 각 카드 뭉치에 속한 카드의 개수는 카드 뭉치의 가장 왼쪽에 있는 카드에 적힌 수보다 작거나 같아야 한다.
• 모든 카드는 정확히 하나의 카드 뭉치에 속해야 한다.

예를 들어 카드 뭉치에 4ドル$장의 카드가 있고 왼쪽부터 카드에 2ドル,ドル 3ドル,ドル 1ドル,ドル 1ドル$이 적혀 있다고 하자. 위의 규칙에 따라 $[2, 3], [1], [1]$ 또는 $[2], [3, 1, 1]$로 카드 뭉치를 나눌 수 있지만 $[2, 1], [3, 1]$ 또는 $[2, 3, 1], [1]$로는 나눌 수 없다.

위의 규칙을 만족하면서 카드 뭉치의 개수가 최소가 되도록 나눴을 때, 그 개수를 구해보자.

입력

첫 번째 줄에 카드의 수 $N$이 주어진다. $(1 \leq N \leq 3\ 000)$

두 번째 줄에 각 카드에 적힌 양의 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 왼쪽에서 $i$번째 카드에 적힌 정수를 의미한다. $(1 \leq A_i \leq N)$

출력

문제의 규칙을 만족하면서 카드 뭉치의 개수가 최소가 되도록 나눴을 때, 그 개수를 출력한다.

제한

힌트