合并神犇
题目背景
loidc 来到了 NOI 的赛场上,他在那里看到了好多神犇。
题目描述
神犇们现在正排成一排在刷题。每个神犇都有一个能力值 $p_i$。loidc 认为坐在附近的金牌爷能力参差不齐非常难受。于是 loidc 便想方设法对神犇们进行人道主义合并。
loidc 想把神犇的能力值排列成从左到右单调不减。他每次可以选择一个神犇,把他合并到两侧相邻的神犇上。合并后的新神犇能力值是以前两位犇的能力值之和。每次合并完成后,被合并的两个神犇就会消失。合并后的新神犇不能再分开(万一他俩有女朋友咋办)因此每次合并后神犇的总数会减 1。
loidc 想知道,想治好他的强迫症需要合并多少次。
输入输出格式
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数,第 $i$ 个整数表示 $p_i$。
输出格式
一行一个整数表示 loidc 需要合并的次数。
输入输出样例
输入样例 #1
8
1 9 9 4 1 2 2 9
输出样例 #1
3
说明
对于 $50\%$ 的数据,$0\lt n \le 5000$。
对于 $100\%$ 的数据,$0\lt n \le2\times 10^5$,$0\lt p_i\le 2147483647$,$p$ 均为随机生成。