탑 쌓기

바이트아저(Byteasar)는 벽돌 $n$개를 사서 $1$번부터 $n$번까지 번호를 매겼습니다. 모든 벽돌의 높이는 같지만 너비는 다를 수 있으며, $i$번 벽돌의 너비는 $w_i$입니다.

바이트아저는 다음 규칙에 따라 모든 벽돌을 여러 층으로 쌓아 탑을 만들려고 합니다.

• 각 층은 하나 이상의 벽돌로 이루어지며, 한 층의 너비는 그 층에 놓인 벽돌들의 너비 합입니다.
• 맨 아래층에서 위로 올라가면서 볼 때, 각 층의 너비는 바로 아래 층의 너비보다 클 수 없습니다. 즉 층의 너비는 아래에서 위로 갈수록 증가하지 않습니다.
• 벽돌은 번호 순서를 지켜야 합니다. 어떤 벽돌도 자신보다 번호가 큰 벽돌보다 더 높은 층에 놓일 수 없습니다. 다시 말해 각 층은 번호가 연속된 벽돌들의 묶음이며, 위로 올라갈수록 번호가 커집니다.
• 모든 벽돌을 반드시 사용해야 합니다.

탑의 높이는 층의 개수입니다. 바이트아저가 쌓을 수 있는 탑의 최대 높이를 구하세요.

첫째 줄에 벽돌의 개수 $n$ ($1 \le n \le 100\,000$)이 주어집니다. 둘째 줄에 $n$개의 정수 $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10\,000$)이 주어지며, $w_i$는 $i$번 벽돌의 너비입니다.

쌓을 수 있는 탑의 최대 높이를 정수 하나로 출력합니다.

너비가 각각 $1$, $2$, $3$인 벽돌 세 개를 생각해 봅시다. $1$번과 $2$번 벽돌을 맨 아래층에 놓으면 그 층의 너비는 $1 + 2 = 3$이고, $3$번 벽돌을 맨 위층에 놓으면 그 층의 너비는 $3$입니다. $3$은 $3$을 넘지 않으므로 이 탑은 규칙을 만족하며, 높이는 $2$가 됩니다.