No.956 Number of Unbalanced
タグ : / 解いたユーザー数 32
作問者 :
kroton
/ テスター :
nmnmnmnmnmnmnm
Problem Statement
For a non-empty integer sequence $X$, if a majority of the elements of $X$ are the same number, then $X$ is called unbalanced.
Examples of unbalanced sequences: $\{1\}$, $\{1, 2, 1\}$, $\{1, 2, 2, 2\}$
Given an integer sequence $A$, count the number of non-empty contiguous subsequences of $A$ that are unbalanced.
Here, subsequences taken from different positions are counted separately, even if they are the same as sequences.
Input
$N$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
All inputs are given as integers.
- $ 1 \leq N \leq 10^5 $
- $ 1 \leq A_{i} \leq 10^5 $
Output
Print a newline at the end.
Sample
Sample 1
Input
6 1 2 2 3 2 3
Output
14
There are the following 14 subsequences.
$\{1\} ,\{1,2,2\} ,\{1,2,2,3,2\}$
$\{2\} ,\{2,2\} ,\{2,2,3\} ,\{2,2,3,2\} ,\{2,2,3,2,3\}$
$\{2\} ,\{2,3,2\}$
$\{3\} ,\{3,2,3\}$
$\{2\}$
$\{3\}$
Sample 2
Input
1 1
Output
1
Sample 3
Input
10 1 1 2 4 2 4 3 4 4 2
Output
25
Sample 4
Input
10 1 7 7 7 3 9 3 1 4 1
Output
21
Sample 5
Input
10 1 1 1 1 1 1 1 1 1 1
Output
55
Sample 6
Input
10 1 2 3 4 5 6 7 8 9 10
Output
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。