Темірулан проти Пернекхана

Темірлану та Пернехану подарували послідовність A з n (1 ≤ n ≤ 5000) цілих додатних чисел. Вони вирішили поділити цю послідовність. Кожен з них має взяти деяку непорожню підпослідовність, причому частина Темірлана повинна починатися раніше, ніж частина Пернехана. Вони прагнуть бути унікальними, тому хочуть, щоб не було жодного числа, яке зустрічається одночасно в частині Темірлана і Пернехана. Айдос, який спостерігав за ними, зацікавився, скільки існує різних способів це зробити. Допоможіть йому, написавши програму для підрахунку кількості таких способів.

Вхідні дані

Перша строка містить ціле число n. Наступна строка містить n цілих чисел A[i] (1 ≤ A[i] ≤ n, 1 ≤ i ≤ n), розділених пробілами.

Вихідні дані

Виведіть єдине число - відповідь на задачу.

Приклади

Примітка

У другому тестовому прикладі існують такі способи поділу:

{ [1] [2] 3 2 }, { [1] [2 3] 2 }, { [1] [2 3 2] },

{ [1] 2 [3] 2 }, { [1] 2 [3 2] }, { [1] 2 3 [2] },

{ [1 2] [3] 2 }, { 1 [2] [3] 2 }, { 1 2 [3] [2] }