count 1 in the array but do not append to your array from the input

Solution for one

1*k <= max(k, x)

For 1st 1 in the array, there are n-1 pairs

For 2nd 1, there are more n-2 pairs

For 3rd 1, there are more n-3 pairs

...

For last 1, supposing there are k 1 in the array, there are more n-k pairs

ans_for_ones = n-1 + n-2 + n-3 + ... + n-k

= n*k - k*(k+1)/2

we will do divide and conquer algorithm and modify merge sort like this

• find max element
• find first index of the max element
• if the max element is side by side consecutively, find its last index too

# in merge_sort method
mx = max(arr[l:r + 1])
midleft = l
for i in range(l, r + 1):
    if arr[i] == midleft:
        midleft = i
        break
midright = midleft
while midright + 1 <= r and arr[midright + 1] == mx:
    midright += 1
merge_sort(l, midleft - 1)
merge_sort(midright + 1, r)

(sorted left_side) (max elements) (sorted right_side) [after using merge sort in smaller segments of the array]

=> (merge left_side and right_side) (max elements) = (sorted array)

For example:

4 1 3 5 1 12 12 12 12* 4 2 12 4 1

1 1 3 4 5 12 12 12 12* 1 2 4 4 12

i = midleft - 1
j = midright + 1
while i >= l and j <= r:
    if arr[i] * arr[j] <= mx:
        ans += i - l + 1 # arr[p] <= arr[i] for p<i, so arr[p]*arr[j] is also less than mx
        j += 1
    else:
        i -= 1

after everything

ans = ans + ans_for_ones

Full code: https://github.com/SR-Hossain/Coding-Platform-Problem-Solve/blob/main/LeetCode/Array%20Pairs.md