You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$，求有多少个三元组 $(i,j,k)$ 同时满足以下两个条件：

• $i < j < k$
• $\min(A_i,A_k)\leq |A_i-A_k|$

格式

输入格式

第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $A_i$。

输出格式

输出一个整数，表示符合条件的三元组的数量。

样例

样例输入 #1

5
4 5 3 1 6

样例输出 #1

4

样例解释 #1

符合条件的三元组有 $4$ 个：$(1,2,4)$，$(1,3,4)$，$(2,3,4)$，$(3,4,5)$。

数据规模

对于 $40\%$ 的数据， $n\leq 100$。

对于 $100\%$ 的数据， $3\leq n\leq 5000$， $1\leq A_i\leq 10^9$。