Submission #62084652

---

Source Code Expand

N = int(input())
A = list(map(int,input().split()))

K = []
for i in range(N):
  K.append([0,N])
  
B = []
for i in range(N):
  B.append([])
for i in range(N):
  B[A[i]-1].append(i)
  
for i in range(N):
  for j in range(len(B[i])):
    t = B[i][j]
    if j != 0:
      K[t][0] = B[i][j-1] + 1
    if i != 0:
      Min = -1
      Max = len(B[i-1])
      while Min+1 != Max:
        Mid = (Min+Max)//2
        if t > B[i-1][Mid]:
          Min = Mid
        else:
          Max = Mid
      if Min != -1:
        K[t][0] = max(K[t][0],B[i-1][Min]+1)
      if Max != len(B[i-1]):
        K[t][1] = B[i-1][Max]
        
ans = 0
for i in range(N):
  ans += (i+1-K[i][0]) * (K[i][1]-i)
  
print(ans)

Submission Info

Judge Result