#XXSY26JAT4. 红军的突击行动

红军的突击行动

红军的突击行动

题目描述

​ 在红军长征途中,先遣队发现前方狭长的山谷中,敌军沿路设立了 n 个连成一排的封锁据点。每个据点都有一定的驻军数量,我们用一个包含 n 个正整数的数组 a 来表示,其中 a[i] 代表第 i 个据点的敌军兵力。 为了以最小的代价突破封锁,红军指挥员制定了如下的“突击战术”:

首先,侦察兵会在当前剩余的所有据点中,找出兵力最多的那个据点作为主攻目标。如果兵力最多的据点有多个,为了尽可能向前推进,红军会选择最靠前(即数组中下标最大)的那个。 随后,红军发起突击,拿下该主攻据点,并顺势将它及其之后(下标>=它)的所有据点全部扫清。

请你编写程序计算,红军总共需要发起多少次“突击行动”,才能将所有据点全部拔除(即数组变为空)?

输入格式

第一行包含一个整数 n(数学公式: 1≤n≤10510^5),表示初始时敌军据点的总数量。

第二行包含 n 个整数 数学公式: a1,a2,…,an(1≤ai≤109)a_1,a_2,…,a_n(1≤a_i≤10^9),依次表示从左到右每个据点的敌军兵力,数字之间用一个空格分隔。

输出格式

​ 输出一行,包含一个整数,表示红军需要发起的突击行动总次数。

输入输出样例

5
2 1 2 3 1
3

5
2 2 2 2 2
5

说明提示

在第一个样例中,数组是 [2,1,2,3,1]。对其执行的操作如下:

首先,选择第 4 个元素。移除最后两个元素,数组变为 [2,1,2];

接着,选择第 3 个元素。移除最后一个元素,数组变为 [2,1];

最后,选择第 1 个元素。移除两个元素,因此在 33 次操作后数组变为空。

在第二个样例中,初始据点兵力为 [2, 2, 2, 2, 2]。

第一次突击:最大兵力为 2,最靠右的是第 5 个据点。拔除它后,剩余 [2, 2, 2, 2]。

后续突击:每次都会选择最靠右的那个据点并只拔除它。总共需要 5 次行动。

数据规模与约定

2≤n≤10510^5