만화

Sophie의 부모님은 Sophie가 가장 좋아하는 만화의 에피소드들을 DVD로 만들었다. Sophie가 보고 싶어 할 때 부모님은 에피소드 구간, 즉 DVD에서 연속한 에피소드들의 나열을 틀어 준다. 안타깝게도 DVD를 만들 때 조금 부주의해서 일부 에피소드가 반복되었고, Sophie는 이 점을 싫어한다. 어떤 에피소드 구간이 Sophie에게 흥미롭다는 것은 그 안에 다른 모든 에피소드와 다른 에피소드가 적어도 하나 존재한다는 뜻이다. 게다가 Sophie는 장난감을 조금 더 가지고 놀고 싶어서 구간의 앞부분 에피소드를 놓치기도 하고, 구간을 끝까지 보지 않아 뒷부분 에피소드를 놓치기도 한다. 따라서 에피소드 구간이 매우 흥미롭다는 것은 그 모든 부분 구간이 흥미롭다는 뜻이다.

Sophie의 부모님은 DVD의 에피소드 구간 중 어느 것이 매우 흥미로운지 궁금해한다. 부모님을 도와 DVD에 담긴 전체 구간이 주어졌을 때 그 부분 구간 중 매우 흥미로운 것의 개수를 구하자.

첫 줄에는 DVD에 담긴 에피소드의 수인 자연수 $n$ ($1 \le n \le 500\,000$)이 주어진다. 둘째 줄이자 마지막 줄에는 $n$개의 자연수가 주어지며, $i$번째 수는 $i$번째 에피소드의 에피소드 번호 $a_i$이다 ($1 \le a_i \le 10^9$).

입력으로 주어진 만화 수열의 매우 흥미로운 구간의 개수를 자연수 하나로 출력한다.

예제 1에서 흥미로운 수열은 길이 1인 모든 수열, 길이 2인 세 수열(길이 2 중에서는 $(6, 6)$만 흥미롭지 않다), 길이 3인 세 수열 모두, 길이 4인 한 수열 $(6, 1, 6, 6)$이다. 이 중에서 $(1, 6, 6)$과 $(6, 1, 6, 6)$은 매우 흥미롭지 않다.

예제 2에서는 전체 수열 $(1, 2, 3, 1, 2, 3)$만 매우 흥미롭지 않다.