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

Темирулану и Пернехану подарили последовательность 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] }