题目描述

Shima has opened an art museum! Its best-known exhibit contains $n$ nanoblobs of various colors arranged in a row. The gap between every pair of adjacent nanoblobs is exactly $10^9$ nanometers, or $1$ meter.

One day, museum reviewer Jerry visits the exhibit. He begins by taking pictures under the following rules:

• If two nanoblobs appear in a picture, every nanoblob between them also appears in that picture.

• No two pictures contain exactly the same collection of nanoblobs.

• Jerry cannot take another picture without violating one of the previous two rules.

Jerry then scores every picture. If all nanoblobs in a picture have distinct colors, its score is $0$. Otherwise, he considers every pair of equally colored nanoblobs, finds the closest such pair, and assigns the picture a score equal to their distance in meters.

Compute the sum of the scores of all Jerry's pictures.

输入格式

The first line contains an integer $n$ ($1\le n\le4\cdot10^5$), the number of nanoblobs.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$), the colors of the nanoblobs from left to right.

输出格式

Output the sum of the scores of all pictures.

5
1 3 2 1 2

9

10
1 4 2 3 5 6 7 10 9 8

0