Description

在神奇的摔跤王国中，最强大的摔跤手们聚集在一起，准备参加一年一度的荣耀大赛。这场比赛不仅是力量的对抗，还是智慧与心理的较量。在赛前的准备阶段，所有选手围坐在篝火，形成一个大圈。每位选手都会从他右手边开始沿逆时针方向观察，评估自己与其他选手的实力对比。 选手们按照顺时针方向排列，每位选手都从他右手边开始沿逆时针方向观察其他选手。当一名选手观察到某位选手预赛成绩低于自己时，他的自信会增加一分。这种自信会一直累积，直至他看到一位预赛成绩不低于自己的选手。我们奖这种持续感受到的自信叫做“自信心增加值”。 你的任务是帮助组织者计算出这种独特的预赛规则下，所有摔跤手的自信心增加值之和。这将帮助他们更好地了解选手们的心理状态，并为最终比赛做出精细的安排。

例如： 当n=6，1～6号选手的预赛成绩分别是 45 25 60 34 80 54。他们按顺时针方向围做成一个圈，面对篝火。 按照比赛规则，我们计算他们的自信心增加值如下： 1号选手（预赛成绩45）观察到6号选手（预赛成绩54），自信心为0. 2号选手（预赛成绩25）观察到1号选手（预赛成绩45），自信心增加值为0. 3号选手（预赛成绩60）观察到2号、1号和6号三位选手（预赛成绩25，45，54）都比他成绩低，直到观察到5号选手预赛成绩比他高，因此自信心增加值为3. 4号选手（预算成绩34）观察到3号选手（预赛成绩60），自信心增加值为0. 5号选手（预赛成绩80）拥有最高的预赛成绩，其观察到的所有其他选手的成绩都比他低，自信心增加值为5. 6号选手（预赛成绩54）观察到5号选手（预赛成绩80），自信心增加值为0。

最终，所有摔跤手的自信心增加值之和等于8（3+5）。

Format

Input

共2行， 第一行包含1个正整数n，表示参赛的摔跤手数量。 第二行，包含n个正整数s_i，分别表示1号到n号每位摔跤手的预赛成绩。 相邻两个整数之间以一个空格隔开。

数据范围： 测试点1～3:1<=n<=1000,1<=s_i<=1000. 测试点4～10：1<=n<=100000,1<=s_i<=1000.

Output

一个整数，表示所有摔跤手的自信心增加值之和。

Samples

6
45 25 60 34 80 54

8

Limitation

1s, 1024KiB for each test case.