Given an array and a number K, count the pairs of positions i < j with a[i] + a[j] ≤ K.
Constraints
- 1 ≤ n ≤ 100000
- −10^9 ≤ a[i], K ≤ 10^9
- The answer can exceed 2^31 − 1.
Input and output
- Input
- Line 1: n K Line 2: n integers
- Output
- One integer: the number of pairs.
Examples
Input 1
4 6
1 5 3 2Output
4(1,5)(1,3)(1,2)(3,2)
Input 2
3 0
1 2 3Output
0No pair fits.
Show hints
- Does the order of the array matter for the count?
- After sorting, if the smallest + largest fits, how many pairs does the smallest make?
Show the explanation
The count does not depend on order, so sort first. Put lo at the start and hi at the end. If a[lo] + a[hi] ≤ K, then a[lo] pairs with every element from lo+1 to hi, adding hi − lo pairs; move lo right. Otherwise a[hi] is too big for any remaining partner; move hi left.
Time: O(n log n) for the sort plus O(n) for the scan. Space: O(1) beyond the sort. Use 64-bit integers for the sum and the count.
Original UniCircle question. Last reviewed 21 Oct 2026.