from collections import defaultdict
from heapq import heapify, heappop, heappush
N = int(input())
A = list(map(int,input().split()))
All = N*(N-1)//2
cnt = 0 #M > m1+m2となるものを数えて最後引く
left = 0 
right = 3
HQ = []
MHQ = []
heappush(HQ,A[0]);heappush(MHQ,-A[0])
heappush(HQ,A[1]);heappush(MHQ,-A[1])
heappush(HQ,A[2]);heappush(MHQ,-A[2])
As = [A[0],A[1],A[2]]; As.sort()
removed = defaultdict(int)
maxremoved = defaultdict(int)
m0,m1,M = As
for left in range(N-2):
    #print(left)
    while right < N and m0 + m1 >= M:
        heappush(MHQ,-A[right])
        
        if A[right] > M: #最大が更新された
            M = A[right]
            heappush(HQ,A[right])
        elif m0 <= A[right] < m1: #小さいほうから二番目が更新された
            m1 = A[right]
            heappush(HQ,A[right])
        elif A[right] < m0: #最小が更新された
            m1 = m0
            m0 = A[right]
            heappush(HQ,A[right])
        #まだ条件を満たさないので右側を動かす
        right += 1
        #print(m0,m1,M,left,right)
    #一度条件を満たしたらその右は全部OK
    #print(left,right,HQ,N+1-right)
    if M > m0+m1:
        #print("cnt+",left,right,m0,m1,M,N+1-right)
        cnt += N + 1 - right
    if right - left <= 3:
        if right >= N: #右側がすでにはみ出した。
            break
        heappush(MHQ,-A[right])
        #最大が更新された
        if A[right] > M:
            M = A[right]
            heappush(HQ,A[right])
        elif m0 <= A[right] < m1: #小さいほうから二番目が更新された
            m1 = A[right]
            heappush(HQ,A[right])
        elif A[right] < m0: #最小が更新された
            m1 = m0
            m0 = A[right]
            heappush(HQ,A[right])
        else:
            heappush(HQ,A[right])
        right += 1
    #最大きい値の場合取り除く作業
    if A[left] == M: #最大値の場合
        heappop(MHQ)
        while maxremoved[MHQ[0]] == 1:
            maxremoved[MHQ[0]] -= 1
            heappop(MHQ)
        M = -1*MHQ[0]
    else:
        maxremoved[A[left]] += 1
    #print("MHQ",MHQ)
    #最小値の場合取り除く作業 
    #print("LEFT",left,A[left],m0,m1)
    if A[left] > m1:
        removed[A[left]] += 1
    elif m0 < A[left] <= m1: #m1が変わる可能性がある
        if removed[A[left]] == 0: #一個しかないので変わる
            heappop(HQ) #m0が取り除かれる（そのまま）
            heappop(HQ) #m1が取り除かれる
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            heappush(HQ,m0) #m0を戻す
        else: #ストックがあった場合には一つ減る
            removed[A[left]] -= 1
    elif m0 <= A[left]: #m0が変わる可能性がある
        if removed[A[left]] == 0: #一個しかないのでm0が更新されてm1がm0, m2がm1となる
            heappop(HQ) #m0が取り除かれる
            m0 = heappop(HQ)
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            heappush(HQ,m0) #m0を戻す
        elif removed[A[left]] == 1: #ちょうど二個の場合にはm0=m1でm1が次に更新
            heappop(HQ) #m0の一個目
            heappop(HQ) #m0の二個目
            while removed[HQ[0]] == 1:
                removed[HQ[0]] -=1
                heappop(HQ)
            m1 = HQ[0] #新しいm1
            removed[A[left]] -= 1 #1個減る
        else:
            removed[A[left]] -= 1 #1個減る

    #print("saigo",left,right,HQ,removed,"M0",m0,"M1",m1,"M",M)
ans = All - cnt
print(ans)