카드 뭉치

앞면에 양의 정수가 적혀 있는 $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)$

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