题目背景

请大家分别用 二分 和 双指针 通过本题

• 1、在 二分 中：请先用 upper_bound 和 lower_bound 实现，再用自己手写二分实现
• 2、在 双指针 中：第一个循环请用 for，用 while 容易写死循环
• 3、参考答案，请大家务必自己动手写一遍！！

题目描述

给定一个长度为 $n$ 的数组 a 和整数 $l, r$ ，请你求出这样的数对 $i, j$ 的个数:

• $0 \le i, j \le n - 1$
• $i < j$
• $l \le a[i] + a[j] \le r$

输入格式

第一行包含 $3$ 个整数 $n, l, r(2 \le n \le 10^5, -10^9 \le l \le r \le 10^9)$

第二行包含 $n$ 个整数，表示数组 $a(-10^9 \le a_i \le 10^9)$

输出格式

输出 $1$ 行包含 $1$ 个数，表示答案

3 4 7
5 1 2

2

5 5 8
5 1 2 4 3

7

4 100 1000
1 1 1 1

0

5 9 13
2 5 5 1 1

1

提示

【样例 1 解释】

• 选择 $i = 0, j = 1(4 \le 5 + 1 \le 7)$
• 选择 $i = 0, j = 2(4 \le 5 + 2 \le 7)$

【数据范围】

对于所有测试数据，均有：

• $2 \le n \le 10^5$
• $-10^9 \le l \le r \le 10^9$
• $-10^9 \le a[i] \le 10^9$

• 特殊性质 A：保证 a 中任意 $2$ 个数之和不超过 $r$（你不用关心右边界）

来源