题目描述

YouTuber Vi Hart 以热爱三角形而闻名。她非常喜欢三角形，以至于想画出尽可能多的不同三角形。

现在她手里有 N 条线段，它们的长度两两不同，且均为整数。她想利用这些长度，构造出所有可能的合法三角形（三角形的三个角都必须大于 0° 且小于 180°）。

旋转和镜像不算不同三角形，也就是说，三角形是否不同只取决于三条边的长度。并且，一条给定长度的线段可以被重复使用多次。

Vi 原本打算写一个程序，给定这些线段长度后，计算可以得到多少个不同的合法三角形。但她只写好了输入输出框架，没有完成核心函数。请你实现程序的主体部分——函数 triangles。

实现细节

你需要实现如下函数：

long long triangles(const int lens[], int n);

该函数只会被调用一次，参数为线段长度数组和数组长度。

你需要向评测系统提交 triangles.cpp 文件，其中实现你的函数。你可以在其中定义任意辅助函数、结构体、变量等；但文件中不能包含 main 函数，并且开头必须通过预处理指令包含头文件：

#include "triangles.h"

数据范围

• 1 ≤ N ≤ 340000
• 1 ≤ 线段长度 ≤ ⌊3N/2⌋

子任务与评分

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

• 子任务 1（10 分）：N ≤ 1750
• 子任务 2（15 分）：N ≤ 8000
• 子任务 3（15 分）：N ≤ 22500
• 子任务 4（10 分）：N ≤ 53000
• 子任务 5（25 分）：N ≤ 130000
• 子任务 6（25 分）：N ≤ 340000

本地测试

题目提供了 triangles.h 与 Lgrader.cpp，你可以将它们与你的程序一起编译进行测试。

运行本地测试程序时，它会先读取 N，再读取所有线段长度。如果你希望以别的方式配置本地测试，可以自行修改题目提供的文件。

样例输入

4
3 6 1 4

样例输出

13

样例解释

合法三角形如下：

1 1 1
1 3 3
1 4 4
1 6 6
3 3 3
3 3 4
3 4 4
3 4 6
3 6 6
4 4 4
4 4 6
4 6 6
6 6 6