Magical Array

Valery는 마법에 매우 관심이 많다. 마법은 그를 너무나 매료하여, 그는 어디에서나 마법을 본다. 그는 이상하고 기묘한 현상이라면 무엇이든 초자연적인 힘의 개입으로 설명한다. 하지만 평범한 수의 배열에서도 Valera가 아름답고 마법 같은 무언가를 찾아낼 줄 누가 알았겠는가.

Valera는 완전히 우연히 수의 배열이 적힌 고대 양피지 조각을 손에 넣었다. 그는 즉시 이 배열의 수들이 무작위가 아니라고 생각했다. 광범위한 연구 끝에 Valera는 마법의 배열이 가져야 할 놀라운 성질을 알아냈다. 배열의 최솟값과 최댓값이 일치하면 그 배열을 마법의 배열이라고 정의한다.

그는 이 뛰어난 발견을 여러분과 공유하기로 했지만, 그 대가로 도움을 요청한다. 엄청난 지성과 재치에도 불구하고 Valera는 계산을 매우 못하므로, 여러분이 그의 작업을 마쳐야 한다. 해야 할 일은 양피지에 적힌 원래 수의 배열에서 마법의 부분 배열의 개수를 세는 것뿐이다. 부분 배열은 연속한 원소들로 이루어진 비어 있지 않은 수열로 정의한다.

입력 데이터의 첫 번째 줄에는 정수 n (1 ≤ n ≤ 105)이 주어진다. 두 번째 줄에는 원래 정수 배열 a1, a2, ..., an ( - 109 ≤ ai ≤ 109)이 주어진다.

마법의 부분 배열의 개수를 나타내는 문제의 답을 한 줄에 출력한다.

C++에서 64비트 수를 읽거나 쓸 때 %lld 서식 지정자를 사용하지 말라. cin, cout 스트림을 사용하는 것이 권장된다. %I64d 서식 지정자를 사용할 수도 있다.

예제 테스트에 대한 참고:

마법의 부분 배열은 시작과 끝의 인덱스 쌍 [a;b]로 나타낸다.

첫 번째 예제: [1;1], [2;2], [3;3], [4;4], [2;3].

두 번째 예제: [1;1], [2;2], [3;3], [4;4], [5;5], [1;2], [2;3], [1;3].