이상한 몸무게 측정 (큰 입력)

"아몬드? 아, 먹어 본 적 있어요. 초콜릿 입힌 거." 두두, 2015년.

두두는 태국 여행을 앞두고 몸을 만드는 중이라 매일 아침 몸무게를 잰다.

며칠 내내 몸무게가 줄어드는 좋은 구간도 있고, 며칠 내내 늘어나는 나쁜 구간도 있다. 그런데 그냥 이상한 구간도 있다.

어떤 구간의 측정값이 증가와 감소를 번갈아 반복하면 그 구간을 이상한 구간이라고 한다. 예를 들어 연속한 날의 측정값이 1, 3, 2, 5, 1이면 이 구간은 이상하다. 1, 3, 5, 4는 1에서 3으로 늘고 다시 3에서 5로 늘기 때문에 이상하지 않다. 이웃한 두 측정값이 같으면 늘어난 것도 줄어든 것도 아니므로, 같은 값이 붙어 있는 구간은 길이가 1인 경우를 빼면 이상하지 않다. 길이가 1인 구간은 모두 이상하다.

측정값 수열이 주어질 때, 이상한 구간이 몇 개인지 센다. 값이 같아도 위치가 다르면 서로 다른 구간으로 센다.

첫째 줄에 수열의 길이 $N$이 주어진다.

둘째 줄에 측정값 $a_1, a_2, \dots, a_N$이 날짜 순서대로 주어진다.

• $1 \le N \le 200\,000$
• $0 \le a_i \le 10^9$

측정값이 이상한 구간, 즉 비어 있지 않은 이상한 구간의 개수를 정수 하나로 출력한다.

수열 1 4 4 2 5 2 1에서 이상한 구간은 [1], [1,4], [4], [4], [4,2], [4,2,5], [4,2,5,2], [2], [2,5], [2,5,2], [5], [5,2], [2], [2,1], [1]이다.

값이 4인 구간은 서로 다른 위치에 두 개 있으므로 두 번 센다.