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

• Обрати два числа (L, R) такi, що 1 ⩽ L ⩽ R ⩽ N. Замiнити всi елементи пiдпослiдовностi AL, AL+1, ..., AR на AL. Скiльки рiзних послiдовностей вiн зможе отримати? Обмеження
• 1 ⩽ N ⩽ 106
• 1 ⩽ Ai ⩽ N Формат вхiдних даних Перший рядок вхiдного потоку мiстить цiле число N - довжину послiдовностi A. Наступний рядок мiстить N цiлих чисел Ai . Формат вихiдних даних У вихiдний потiк вивести одне число - кiлькiсть рiзних послiдовностей.

Input Specification

Output Specification