테스트 준비

닉은 프로그래밍 대회에 낼 문제를 준비하고 있다. 대회가 임박했지만 아직 테스트를 만들지 못했다. 테스트 생성을 간단히 하려고 멀티테스트 방식을 쓰기로 했다. 입력 하나에는 테스트가 하나 이상 들어 있고, 각 테스트는 앞 테스트 바로 뒤에 이어 붙는다.

각 테스트는 정수 $m$로 시작하고, 이어서 정수 쌍 $a_i, b_i$가 $m$개 나온다. 각 쌍은 무방향 그래프의 간선을 나타낸다. 정점은 0번부터 번호가 매겨지며 번호의 상한은 없다. 한 테스트의 그래프에는 루프나 다중 간선이 없어야 하고, 사이클이 없는 포레스트여야 한다.

닉은 다른 문제에서 쓰던 음이 아닌 정수 배열을 이번 문제에도 쓰기로 했다. 닉은 이 배열의 부분 배열을 골라 테스트로 사용한다. 배열의 서로 다른 부분 배열 중 이 문제의 올바른 입력이 되는 것의 개수를 구하라. 두 부분 배열은 시작 인덱스나 끝 인덱스 중 하나라도 다르면 서로 다르다.

첫 줄에 배열의 원소 개수 $n$이 주어진다 ($1 \le n \le 500\,000$). 둘째 줄에는 배열의 원소 $a_i$가 $n$개 주어진다 ($0 \le a_i \le 10^9$).

올바른 입력이 되는 서로 다른 부분 배열의 개수를 한 줄에 출력한다.

첫 번째 예시에서 올바른 입력이 되는 부분 배열은 대괄호로 표시한 [2 1 3 4 1]과 2 [1 3 4] 1이다.

두 번째 예시에서는 [1 3 1] 2 2 0 2 3, 1 [3 1 2 2 0 2 3], 1 3 1 [2 2 0 2 3], 1 3 1 2 2 [0] 2 3, [1 3 1 2 2 0 2 3]이 올바른 입력이다.