问题描述

小杨的班级里共有N名同学，学号从0至N-1。老师安排全班同学依次进入教室，每位同学进入时，需要和已经在教室内且学号小于自己的同学握手。求整个班级总共会进行多少次握手。

提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。

输入描述

输入共2行：

1. 第一行一个整数N，表示同学的个数；
2. 第二行N个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0~N-1之间，表示该同学的学号。

保证每位同学会且只会进入教室一次。

输出描述

输出一行一个整数，表示全班握手的总次数。

特别提醒：请不要在输入、输出中附带任何提示信息。

样例1

输入

4
2 1 3 0

输出

2

解释

• 2号同学进入：教室无人，握手0次；
• 1号同学进入：教室仅有2号同学，1号学号更小，无需握手，累计0次；
• 3号同学进入：教室有1、2号同学，学号均小于3，握手2次，累计2次；
• 0号同学进入：教室所有同学学号都更大，无需握手，累计2次。

总握手次数为2。

样例2

输入

6
0 1 2 3 4 5

输出

15

解释

每位同学进入时，学号都是当前教室最大的，总握手次数为0+1+2+3+4+5=15。

数据规模

• 对于30%的测试点，保证N≤100；
• 对于所有测试点，保证2≤N≤3×10^5。