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]이다.