이상한 체중 기록 (중간)

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

두두는 곧 떠날 태국 여행을 앞두고 몸을 만들고 있다. 계획의 하나로 매일 아침 체중을 기록한다.

며칠 동안 체중이 꾸준히 줄어드는 구간도 있고, 꾸준히 늘어나는 구간도 있다. 그런데 이상하게 움직이는 구간도 있다.

어떤 구간의 기록이 증가와 감소를 번갈아 반복하면 그 구간을 이상한 구간이라고 한다. 예를 들어 연속한 날의 기록이 1, 3, 2, 5, 1이면 이 구간은 이상하다. 기록이 1, 3, 5, 4이면 1에서 3으로, 다시 3에서 5로 두 번 연속 증가하므로 이상하지 않다. 길이가 1인 구간은 모두 이상하다.

이웃한 두 기록이 같으면 그 변화는 증가도 감소도 아니므로, 두 기록을 함께 포함하는 구간은 이상하지 않다.

기록의 수열이 주어지면 이상한 구간이 몇 개인지 구하라.

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

둘째 줄에 수열을 이루는 $N$개의 정수 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

• $1 \le N \le 5000$
• $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]의 15개다. 기록 4 하나로 이루어진 구간이 두 개 있고, 위치가 다르므로 둘 다 센다.