У Степана нове хобі - він уже тиждень грається із різними послідовностями чисел. Сьогодні у нього чекає вирішення цікава задача. Степан хоче порахувати кількість різних послідовностей, які можна отримати із даної послідовності цілих чисел ~A~ довжиною ~N~, виконавши один раз таку операцію:

• Обрати два числа ~(L,R)~ такі, що ~1 \le L \le R \le N~. Замінити всі елементи підпослідовності ~A_L,A_{L+1},...,A_R~ на ~A_L~.

Скільки різних послідовностей він зможе отримати?

Обмеження

• ~1 \le N \le 10^6~
• ~1 \le A_i \le N~

Input

Перший рядок вхідного потоку містить ціле число ~N~ - довжину послідовності ~A~.

Наступний рядок містить ~N~ цілих чисел ~A_i~.

Output

У вихідний потік вивести одне число - кількість різних послідовностей.

Sample Input 1

4
1 1 2 3

Sample Output 1

4

Notes

Можливі такі різні послідовності:

- (1,1,1,1)

- (1,1,1,3)

- (1,1,2,2)

- (1,1,2,3)