三角形
- 时间限制：1 秒
- 内存限制：256 MB
- 输入：标准输入
- 输出：标准输出
题目描述
格鲁的女儿们最喜欢的几何图形是三角形。在空闲时间，她们喜欢玩一个游戏：每人选择一个正整数，然后一起检查是否能以这些数为边长构成一个非退化三角形。
有一天，她们在家里找到了一个包含 $n$ 个正整数的集合 $a$。现在她们想知道有多少个整数 $x$，使得 $x$ 与集合 $a$ 中的任意两个数总能构成某个非退化三角形的边长。请帮助她们解决这个问题。
输入格式
第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$）。
第二行包含 $n$ 个整数，即集合 $a$ 中的数（$1 \le a_i \le 10^9$）。
输出格式
输出一个整数，表示答案。
评分系统
每道子题的分数只有在通过该子题及所有必要子题的所有测试时才给予。
| 子任务 | 分数 | 限制 | 必要子任务 | 评测信息 |
|---|---|---|---|---|
| 0 | – | 样例 | 无 | 完全 |
| 1 | 14 | $n \le 500$；$a_i \le 200$ | 0 | 完全 |
| 2 | 15 | $n \le 2000$；$a_i \le 500$ | 0, 1 | 首次错误 |
| 3 | 11 | $a_i \le 4$ | 无 | 首次错误 |
| 4 | 13 | $a_i = a_j$ 对所有 $i,j$ | 无 | 首次错误 |
| 5 | 14 | $a_1 = 1$ | 无 | 首次错误 |
| 6 | 16 | $a_i \le 2 \cdot 10^5$ | 0, 1, 2, 3 | 首次错误 |
| 7 | 17 | 无额外限制 | 0 – 6 | 首次错误 |
示例
示例 1
输入
3
3 3 5输出
3示例 2
输入
3
3 1 2输出
0示例 3
输入
5
9 5 6 7 9输出
6