Description

石老板为了装修迎新晚会，拿了一根彩灯=== 有一个长度为n（不超过10万）的彩灯条。上面的每一个彩灯珠可以用一个不超过1e18的整数表示其颜色。问选择一串不含重复颜色灯珠的灯珠条，有多少种选法，只要开始位置不同，就认为是不同的选法。

Input

第1行一个n，表示灯珠串的长度。 第2行含有由空格分隔的n个数，表示每个灯珠的颜色。

Output

方案数

Samples

5 
1 1 2 1 5

9

Limitation

1s, 1024KiB for each test case.