能量收集器

题目描述

史前遗迹是由一列高矮不同的柱子组成。每一根柱子，会和它后面比它矮的柱子组成一个能量收集器，但是和它前面的柱子不能组成能量收集器，柱子可以重复使用。给出一列柱子的高度，求可以组成多少个能量收集器，没有能组成能量收集器的柱子，输出0。

输入格式

共 2 行。第一行输入一个整数 $n$（$1 \le n \le 100000$）。 第二行输入 $n$ 根柱子的高度，每个高度为正整数。

输出格式

能够组成能量收集器的数量。

样例输入 #1

6
9 7 5 8 3 10

样例输出 #1

8

数据范围

$1 \le n \le 100000$ 柱子高度为正整数，不超过 $10^9$。

知识点与难度

本题涉及的知识点从属于 GESP 五级（归并排序、分治、逆序对计数），难度等级：⭐⭐⭐⭐。

测试点分布