e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Temirulan vs Pernekhan

Temirulan vs Pernekhan

Темирулану и Пернехану подарили последовательность A из n (1n5000) целых положительных чисел. Они договорились поделить эту последовательность. Каждый из них должен взять некоторую не пустую последовательную часть последовательности, причем часть Темирулана должна начинаться раньше части Пернехана. Они хотят выглядеть уникально, поэтому они хотят чтобы не существовало ни одного числа, встречающегося в участке Темирулана и Пернехана одновременно. Айдос, наблюдавший за ними, заинтересовался, сколько существует различных способов сделать это. Помогите ему, напишите программу для количества способов.

Входные данные

Первая строка содержит целое число n. Следующая строка содержит n целых чисел Ai (1Ain, 1in), разделенных пробелами.

Выходные данные

Выведите единственное число - ответ на задачу.

Пояснение

Во втором тестовом примере имеются следующие способы разделения:

{ [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] }

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
3
1 2 3
Output example #1
5
Input example #2
4
1 2 3 2
Output example #2
9
Input example #3
1
1
Output example #3
0
Source 2015 Казахстан, 4-й этап Республиканской олимпиады по информатике, Уральск, 13-18 марта, Задача C