思路

对固定中间位置$j$，记$y=a_j$。令频次函数为$f(x)$，并定义

• $G(t)$：数组中$\ge t$的元素个数，
• $L(t)$：数组中$\le t$的元素个数。

由条件$\max(a_i-a_j,a_j-a_k)=2a_j$可拆分为两种达到最大值的方式，并用容斥合并：

• 当$a_i-a_j=2a_j$时，$a_i=3y$且$a_j-a_k\le 2y \Rightarrow a_k\ge -y$，贡献为$f(3y)\cdot G(-y)$；

题目内容

小红拿到一个长度为 $n$ 的数组 {$a_1,a_2,…,a_n$} 。

她想要知道有多少个三元组 $(i,j,k)$ 满足 $max(a_i-a_j,a_j-a_k)=2×a_j$ 。

请你帮她数一数。

输入描述

第一行输入一个整数 $n(3 ≦n ≦ 2×10^5)$ 代表数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^9≦a_i≦10^9)$ ，表示数组中的元素。

输出描述

输出一个整数，表示满足条件的三元组个数。

样例1

输入

3
0 1 -1

输出

6

说明

在这个样例中，满足条件的三元组选取为

• $(i,j,k)=(1,1,1)$ ，此时左边 $max$ {$0-0,0-0$} $=0$ ，右边 $2×a_1=0$ ；

• $(i,j,k)=(1,1,2)$ ，此时左边 $max$ {$0-0,0-1$} $=0$ ，右边 $2×a_1=0$ ；

• $(i,j,k)=(1,2,3)$ ，此时左边 $max$ {$0-1,1-(-1)$} $=2$ ，右边 $2×a_2=2$ ；

• $(i,j,k)=(2,2,3)$ ，此时左边 $max$ {$1-1,1-(-1)$} $=2$ ，右边 $2×a_2=2$ ；

• $(i,j,k)=(3,1,1)$ ，此时左边 $max$ {$-1-0,0-0$} $=0$ ，右边 $2×a_1=0$ ；

• $(i,j,k)=(3,2,3)$ ，此时左边 $max$ {$-1-1,1-(-1)$} $=2$ ，右边 $2×a_2 =2$ 。

样例2

输入

4
0 0 -1 1

输出

20