Farmer John의 소 연합(UCFJ)은 International bOvine olympIad(IOI)에 대표단을 보냅니다.

대표단 선발에 $N$마리의 소가 참가합니다($1 \leq N \leq 2 \cdot 10^5$). 소들은 한 줄로 서 있으며 소 $i$의 품종은 $b_i$입니다.

대표단은 적어도 두 소로 이루어진 연속 구간, 즉 $1\le l<r\le N$을 만족하는 정수 $l$, $r$에 대한 소 $l\ldots r$로 구성됩니다. 구간 양 끝의 두 소를 “지도자”로 지정합니다. 같은 품종 안에서의 갈등을 피하려면 각 지도자의 품종이 지도자 여부와 관계없이 대표단의 다른 모든 소의 품종과 달라야 합니다.

세금 문제 때문에, UCFJ가 IOI에 보낼 대표단을 고르는 방법의 수를 구하도록 도와주세요.

입력

첫 번째 줄에는 $N$이 주어집니다.

두 번째 줄에는 $[1,N]$ 범위의 정수 $b_1,b_2,\ldots,b_N$이 $N$개 주어집니다.

출력

가능한 대표단의 수를 한 줄에 출력합니다.

정수가 크므로 64비트 정수 자료형(예를 들어 C/C++의 long long)이 필요할 수 있습니다.

예제

입력 1

7
1 2 3 4 3 2 5

출력 1

13

참고

각 대표단은 다음 지도자 쌍 중 하나에 대응합니다.

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

서브태스크

• 테스트 케이스 1–3은 $N\le 100$을 만족합니다.
• 테스트 케이스 4–8은 $N\le 5000$을 만족합니다.
• 테스트 케이스 9–20에는 추가 제한이 없습니다.

문제 출처: Benjamin Qi