Count perfect pairs

Problem A pair of integers (x, y) is perfect if both conditions hold: min(|x−y|, |x+y|) <= min(|x|, |y|) and max(|x−y|, |x+y|) >= max(|x|, |y|). Given an integer array arr of length n, count the number of perfect pairs (arr[i], arr[j]) with 0 <= i < j < n.

Input / Output

• Input: int arr[n] — an array of integers (values may be negative).
• Output: long — the number of perfect pairs. The count can reach ~n²/2, which overflows a 32-bit int.

Constraints

• 2 <= n <= 10^5
• Values may be negative; take care that abs(INT_MIN) overflows in most languages — widen before taking the absolute value.

Example

• arr = [2, 5, −3] → 2. (2, 5) fails: min(|2−5|, |2+5|) = 3 > min(2, 5) = 2. (2, −3) passes: min(5, 1) = 1 <= 2 and max(5, 1) = 5 >= 3. (5, −3) passes: min(8, 2) = 2 <= 3 and max(8, 2) = 8 >= 5.