class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def add(self, i, x): while i <= self.size: self.tree[i] += x i += i & -i def sum(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & -i return s def lb(self, x): sv = 0 svid = 0 topid = pow(2,(self.size).bit_length()-1) while topid: if svid + topid <= self.size and sv + self.tree[svid+topid] <= x: sv += self.tree[svid+topid] svid += topid topid //= 2 return svid + 1 n=int(input()) a=list(map(int,input().split())) bit=Bit(n) for i in range(1,n+1): bit.add(i,1) x,y=0,0 for i in range(n-1,-1,-1): t=bit.lb(a[i]) if t == n+1: t1=bit.lb(a[i]-1) if t1 != n+1: bit.add(a[i],-1) else: t2=bit.lb(0) bit.add(t2,-1) y += i+1 else: bit.add(t,-1) x += i+1 print(x-y)