N마리(N ≤ 3 × 10^5)의 소들의 키는 1, 2, …, N이다.

어느 날, 소들이 프리소비(소들이 가지고 노는 프리스비라서 프리소비라고 부른다)를 가지고 놀며 어떤 순서로 줄을 서 있다.

소들은 h_1, …, h_N 높이로 줄을 서있다(따라서 h는 1 … N의 순열이다).

i와 j 위치에 있는 두 마리의 소는 그 사이의 모든 소의 높이가 min(h_i, h_j)보다 낮은 경우에만 프리소비를 앞뒤로 성공적으로 던질 수 있다.

프리소비를 앞뒤로 성공적으로 던질 수 있는 한 쌍의 소가 있는 위치 i<j의 모든 쌍 사이의 거리의 합을 계산하시오.

위치 i와 j 사이의 거리는 j−i+1이다.

프리소비 (Cow Frisbee) timer 2초 memory 256MB

프리소비 (Cow Frisbee) 2초 256MB