F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Array

Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1396    Accepted Submission(s): 445


Problem Description
Given an integer array $a[1..n]$.

Count how many subsegment $[L, R]$ satisfying $R - L + 1 \geq 1$ and there is a kind of integer whose number of occurrences is strictly greater than the sum of others in $a[L..R]$.
 

Input
The first line contains an integer $T(T \le 15)$. Then $T$ test cases follow.

For each test case, input two lines.

For the first line, there is only one integer $n$ $(1 \leq n \leq 10^6)$.

The second line contains $n$ integers describing the array $a[1..n]$, while the restriction $0 \leq a_i \leq 10^6$ is guaranteed.

$\sum n<=6*10^6$
 

Output
For each test case, output a integer per line, denoting the answer of the problem.
 

Sample Input
1 10 3303 70463 3303 3303 3303 70463 3303 3303 70463 70463
 

Sample Output
47
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 08:15:17, Gzip enabled