Chef and Dominating Subarrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef likes problems with arrays. Let's call an array V dominating if there exists a number x (the dominator) whose number of occurrences is strictly greater than half the size of the array (that is, floor(V/2)).
For example, the arrays {1, 2, 1} is dominating, with the number 1 being the dominator, since half the size of the array is 1, while the number 1 occurs twice. Similarly, the array {1, 1, 1, 2} is dominating. On the other hand, the arrays {1, 2, 3} and {1, 2, 2, 1} are not dominating.
Given an array A consisting of N positive integers, you need to help Chef find the number of subarrays of A which are dominating.
Input
The first line of input contains one integer N denoting the number of elements in the array A. The second line of input contains N spaceseparated integers denoting the array A.
Output
Output the answer to the query in a single line.
Constraints
 1 ≤ N ≤ 5 × 10^{5}
 1 ≤ A_{i} ≤ 10^{9}
Example
Input: 5 1 2 1 2 1 Output: 9 Input: 7 1 2 3 3 2 1 3 Output: 11
Subtasks
 Subtask 1: N ≤ 10^{2}. Points  10
 Subtask 2: N ≤ 10^{4}. Points  20
 Subtask 3: N ≤ 10^{5}. Points  30
 Subtask 4: Original constraints. Points  40
Explanation
Test #1:
The dominating subarrays are A[1..1], A[2..2], A[3..3], A[4..4], A[5..5], A[6..6], A[1..3], A[2..4], A[3..5].
Test #2:
The dominating subarrays are A[1..1], A[2..2], A[3..3], A[4..4], A[5..5], A[6..6], A[7..7], A[3..4], A[2..4], A[3..5], A[3..7].
Author:  mgch 
Editorial  http://discuss.codechef.com/problems/CHEFDOMA 
Tags  decomposition, ltime33, medhard, mgch, sqrt 
Date Added:  6022016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 