from collections import deque class SWAG: def __init__(self, operator_M, e_M): self.op_M = operator_M self.e_M = e_M self.q = deque() self.accL = [e_M] self.accR = e_M self.L = self.R = 0 def build(self,lst): self.q = deque(lst) self.L = len(lst) for i in reversed(lst): self.accL.append(self.op_M(i,self.accL[-1])) def __len__(self): return self.L + self.R def fold_all(self): return self.op_M(self.accL[-1],self.accR) def append(self,x): self.q.append(x) self.accR = self.op_M(self.accR,x) self.R += 1 def popleft(self): if self.L: self.accL.pop() self.L -= 1 return self.q.popleft() elif self.R: v = self.q.popleft() self.L,self.R = self.R-1,0 for i in reversed(self.q): self.accL.append(self.op_M(i,self.accL[-1])) self.accR = self.e_M return v else: assert 0 n = int(input()) *a, = map(int,input().split()) def f(A,B): a,b,m1 = A c,d,m2 = B if a < c: return (a,min(c,b),max(m1,m2)) else: return (c,min(a,d),max(m1,m2)) INF = 1<<60 swag = SWAG(f,(INF,INF,0)) def check(R): x,y,M = swag.fold_all() return max(M,a[R]) <= x+min(y,a[R]) ans = R = 0 for L in range(n): while L==R or (R < n and check(R)): swag.append((a[R],INF,a[R])) R += 1 ans += R-L-1 swag.popleft() print(ans)