The head gardener planted a long path of flower plots, and every plot holds exactly one species of flower, encoded as a species ID. To score how visually varied each section of the path is, the gardener looks at every contiguous stretch of plots (a single plot counts too, and so does the entire path), counts how many distinct species appear in that stretch, and squares the count. Add up these squared diversity scores across every possible contiguous stretch and report the grand total.

Input format

• Line 1: a single integer n, the number of plots along the path.
• Line 2: n space-separated integers, the species ID planted in each plot, in path order.

Output format

Print a single integer: the sum, over every contiguous stretch of plots, of the square of the number of distinct species in that stretch.

Constraints

• 1 ≤ n ≤ 2000
• 1 ≤ species ID ≤ 10^5

3
1 2 1

15

1
4

1