题目描述

给定一个序列 $a_1, a_2,\cdots,a_n$，请将它分割成若干段，满足以下两个条件：

• 首先，每一段内的数字在原序列中，必须是相邻的。
• 其次，每一段数字之和必须大于或等于上一段数字之和。

满足相邻性与单调性的分割方案称之为金字塔分割，请找到一个金字塔分割方案，且分割后的段落数量（也就是金子塔的高度）最大。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$个整数 $a_1,a_2,\cdots,a_n$

输出格式

• 单个整数：表示金字塔的最高高度

5
1 2 3 4 5

5

5
5 4 3 2 1

2

数据范围

• $30\%$ 的数据，$1\leq n\leq 200$
• $60\%$ 的数据，$1\leq n\leq 2000$
• $100\%$ 的数据，$1\leq n\leq 200,000$
• $1\leq a_i\leq 10000$