Slimes - MarisaOJ: Marisa Online Judge

There are

$n$ slimes standing in a row, the

$i^{th}$ one has size

$A_i$ . Merging two slimes of the same size

$i$ will result in a slime of size

$i + 1$ . Count the number of pairs

$l \le r$ that merging all slimes

$l,l+1,...,r$ results in one slime. ### Input - The first line contains an integer

$n$ . - The next line contains

$n$ integers

$A_i$ . ### Output - Print the number of pairs. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le A_i \le 10^9$ . ### Example Input:

$3 1 1 2$

Output:

$5$

Topic

Hashing

Divide and conquer

Rating

2200

Solution (0)

Solution