Izbori

Malnar 씨는 Tompojevci 군의 군수를 뽑는 선거에 출마한다. Tompojevci 군은 Tompojevci라는 마을 하나로 이루어져 있고, 마을에는 1번부터 $n$번까지 번호가 붙은 $n$채의 집이 일렬로 늘어서 있다. 각 집에는 주민이 한 명씩 살고, Malnar 씨에게 중요한 것은 그 주민이 유권자라는 점이다. Malnar 씨는 선거에서 가장 좋은 후보가 이기는 게 아니라 선거 전에 가장 좋은 연회를 여는 후보가 이긴다는 것을 안다. 그래서 선거 며칠 전에 연회를 열 계획이다. 번호가 $l$ 이상 $r$ 이하($l ≤ r$)인 집에 사는 마을 주민을 모두 초대하고 맛있는 음식을 대접한다.

Malnar 씨는 Tompojevci의 주민을 모두 잘 알기 때문에 각 주민이 가장 좋아하는 음식이 무엇인지도 안다. 그래서 연회에서는 초대한 사람들 중 과반수가 가장 좋아하는 음식을 준비한다. 다만, 자신이 가장 좋아하는 음식을 받은 사람만 Malnar 씨에게 투표하고, 나머지는 유일한 다른 후보인 Vlado 씨에게 투표한다. 선거에서 이기려면 Malnar 씨는 투표한 사람들로부터 과반수보다 많은 표를 얻어야 한다. 연회에 초대받지 못한 주민은 선거를 잊어버리고 투표하지 않는다.

Malnar 씨는 이제 자신이 선거에서 이기도록 $l$과 $r$을 고르는 서로 다른 방법이 몇 가지인지 알고 싶어 한다.

첫째 줄에 양의 정수 $n$($1 ≤ n ≤ 200\,000$)이 주어진다.

둘째 줄에 $n$개의 양의 정수 $a_i$($1 ≤ a_i ≤ 10^9$)가 주어지며, 각각 $i$번 집에 사는 주민이 가장 좋아하는 음식을 나타낸다.

Malnar 씨가 선거에서 이기도록 $l$과 $r$을 고르는 서로 다른 방법의 수를 한 줄에 출력한다.

두 번째 예제에 대한 설명: 가능한 ($l$, $r$)의 선택은 (1, 1), (2, 2), (3, 3), (1, 3)이다.