import random
random.seed(6)
seznam_ljudi = [random.randrange(-10**9, 10**9) for i in range(500000)]


# Ideja: seznam uredimo in se zapeljemo cez njega. Upostevamo le
# sosede na desni, drugace bi vsak par dvakrat steli.
# V nekem trenutku smo v seznamu na nekem cloveku. Recimo, da ima
# na desni 10 sosedov. Ko se premaknemo na naslednjega cloveka,
# pogledamo le tiste nove ljudi na desni, za katere je razdalja
# do njih dovolj majhna. Ker je seznam urejen, so to vsi sosedi.
def sosedi(seznam_ljudi, razdalja):
    seznam_ljudi.sort()
    n = len(seznam_ljudi)
    stevilo_sosedov = 0
    # Spodnji kazalec si zapomni, kje lezi najbolj oddaljeni
    # sosed trenutnega cloveka. (V resnici si zapomni pozicijo
    # prvega cloveka, ki ni vec sosed.)
    zadnji_sosed = 1
    
    for clovek in range(n):
        while zadnji_sosed < n and (
            seznam_ljudi[zadnji_sosed] - seznam_ljudi[clovek] <= razdalja):
            zadnji_sosed += 1
        stevilo_sosedov += (zadnji_sosed - 1) - clovek
        
    return stevilo_sosedov

print(sosedi(seznam_ljudi, 10000000))