Given an array of n integers, a contiguous subarray is called dominant if some single value occurs strictly more than half of the subarray's length within it (equivalently, more than every other value combined). Count the number of dominant contiguous subarrays (index ranges [i, j] with i ≤ j), out of all n(n+1)/2 possible contiguous subarrays.
Input format
Line 1: an integer n.
Line 2: n space-separated integers (the array).
Output format
A single integer: the number of dominant contiguous subarrays.
Constraints
- 1 ≤ n ≤ 2000
- -1000000000 ≤ each value ≤ 1000000000