Description

已知一个包含 n 个非负整数的数组 a，要从中选出三个数作为三角形的三条边的边长， 

有多少种不同的选法。

注意：要组成三角形需要满足的条件是任意两边之和大于第三边。 

Input Format

第一行为一个正整数 n。 

第二行 n 个空格隔开的非负整数。

Output Format

满足条件的方案数。 

4 
2 2 3 4

3

Hint

【样例解释】 

可选的方案：（1）2、2、3 （2）2（第一个 2）、3、4 （3）2（第二个 2）、3、4 

【数据范围】 

30%数据，n<=100,0≤a[i]≤1000 

100%数据，n<=2500,0≤a[i]≤1000 

Source

南海区镇赛 桂城小学2022A 前缀和 下标计数 二分查找