Help me in solving COUNTARI problem

help
,
1

My issue

  • What is the expected time complexity for this question?
  • If less then O(n^2), someone please explain their approach… or
    just hint like what is to be used?
    I just can’t do better than O(n^2).

My code

from collections import defaultdict as dd

n = int(input())
a = list(map(int,input().split()))


rights = dd(lambda:0)


lefts = [a[0]]
for i in range(1,n):
    rights[a[i]] += 1   
    
ans = 0
for i in range(1,n):
    ele = a[i]
    rights[ele] -= 1
    for left in lefts:
        if rights[2*ele-left] >= 1:
            ans += rights[2*ele-left]
    lefts.append(ele)
    

print(ans)

Problem Link: COUNTARI Problem - CodeChef