题目背景

老师手里有一组整数，想考考同学们：其中有多少个数，恰好等于另外两个不同位置上的数之和？每个符合条件的数只统计一次。

题目描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$（允许有负数和 $0$，数值可能重复，但每个位置是独立的）。

请统计：有多少个下标 $k$，存在两个与 $k$ 不同、且互不相同的下标 $i,j$，使得

只要 $a_k$ 能被表示出来，就计数一次；即使它有多种表示方式，也只算一次。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示满足条件的下标个数。

样例输入1

6
1 2 3 4 5 6

样例输出1

4

样例解释1

• $3=1+2$，$4=1+3$，$5=1+4$（或 $2+3$），$6=1+5$（或 $2+4$），均可表示；
• $1$ 和 $2$ 无法由两个不同位置上的数相加得到。

答案为 $4$。

样例输入2（稍大，含负数和 0）

12
-3 0 3 -1 1 2 -2 6 4 5 -6 8

样例输出2

11

样例解释2

除 $-6$ 外其余 11 个数都能由另外两个不同位置上的数相加得到，例如：

$(-3)+3=0$，$3+(-1)=2$，$(-3)+(-2)=-5$（不存在），而 $-6$ 无法凑出。

注意 $(-2)+(-4)=-6$ 中 $-4$ 并不存在，因此 $-6$ 不能被表示。

数据范围与约定

• $3\le n\le 2000$
• $|a_i|\le 10^9$
• 三个下标必须互不相同（$i,j,k$ 是三个不同的位置）；
• 答案可能超过 32 位有符号整数范围，建议使用 64 位整数。

提示

朴素的三重循环是 $O(n^3)$，无法通过最大数据。可以先排序，然后枚举作为"和"的元素 $a_k$，在剩余元素上用双指针从两端向中间找一对数之和等于 $a_k$，一次查找 $O(n)$，总复杂度 $O(n^2)$。注意双指针区间内不能包含位置 $k$，且 $a_i$ 可以是负数，不能简单地"和太大就只往右缩"。