중간 뒤집기

길이가 $N$인 수열 $A$에서, $1\le i\le j\le N$에 대하여 $f(i,j)$를 $A$의 $i$번째부터 $j$번째 원소까지의 연속된 부분수열을 뒤집어서 얻어진 수열로 정의한다. 예를 들어, $A=[3,1,4,1,5]$라면 $f(2,3) =[3,4,1,1,5]$, $f(1,5) =[5,1,4,1,3]$, $f(1,1) =[3,1,4,1,5]$이다.

$f(i,j)$에서 $i$와 $j$를 정하는 경우의 수는 $\displaystyle \frac{N(N+1)}{2}$가지가 있다. 수열 $A$가 주어질 때, 모든 $f(i,j)$ 중 서로 다른 수열의 개수를 구하여라.

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. ($1\le N\le 500\, 000$)

둘째 줄에 $A$의 원소를 의미하는 $N$개의 정수 $A_{1},A_{2},\cdots ,A_{N}$이 공백으로 구분되어 주어진다. ($1\le A_{i}\le 10^{9}$)

$f(i, j)$로 가능한 서로 다른 수열의 개수를 출력한다.