Cho một mảng số nguyên nums được đánh chỉ mục từ 0 có độ dài là n và một số nguyên target, hãy trả về số cặp (i, j) sao cho 0 <= i < j < n và nums[i] + nums[j] < target.

Ví dụ 1:

Input: nums = [-1, 1, 2, 3, 1], target = 2

Output: 3

Giải thích: Có 3 cặp chỉ mục thỏa mãn điều kiện trong đề bài:

• (0, 1) vì 0 < 1 và nums[0] + nums[1] = 0 < target
• (0, 2) vì 0 < 2 và nums[0] + nums[2] = 1 < target
• (0, 4) vì 0 < 4 và nums[0] + nums[4] = 0 < target

Lưu ý rằng (0, 3) không được tính vì nums[0] + nums[3] không nhỏ hơn target.

Ví dụ 2:

Input: nums = [-6, 2, 5, -2, -7, -1, 3], target = -2

Output: 10

Giải thích: Có 10 cặp chỉ mục thỏa mãn điều kiện trong đề bài:

• (0, 1) vì 0 < 1 và nums[0] + nums[1] = -4 < target
• (0, 3) vì 0 < 3 và nums[0] + nums[3] = -8 < target
• (0, 4) vì 0 < 4 và nums[0] + nums[4] = -13 < target
• (0, 5) vì 0 < 5 và nums[0] + nums[5] = -7 < target
• (0, 6) vì 0 < 6 và nums[0] + nums[6] = -3 < target
• (1, 4) vì 1 < 4 và nums[1] + nums[4] = -5 < target
• (3, 4) vì 3 < 4 và nums[3] + nums[4] = -9 < target
• (3, 5) vì 3 < 5 và nums[3] + nums[5] = -3 < target
• (4, 5) vì 4 < 5 và nums[4] + nums[5] = -8 < target
• (4, 6) vì 4 < 6 và nums[4] + nums[6] = -4 < target

Ràng buộc:

• ~1 < nums.length == n \leq 10^5~
• ~-10^9 < nums[i], target \leq 10^9~

INPUT

• Dòng đầu: Gồm số nguyên n .
• Dòng tiếp theo: Gồm dãy số nums.
• Dòng cuối: Gồm số nguyên target.

OUTPUT

• Một số nguyên là kết quả bài toán.

Sample Input

5
-1 1 2 3 1
2

Sample Output

3