Республиканская олимпиада по информатике, 2015 год, 10-11 класс

Задача C. Temirulan vs Pernekhan

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

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

Первая строка входных данных содержит целое число $N$. Следующая строка содержит $N$ целых чисел $1 \le A_i \le N$, $1 \le i \le N$, разделенных пробелами.

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

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

Примеры:

1.Вход:

3
1 2 3 

Ответ:

5

2.Вход:

4
1 2 3 2

Ответ:

9

3.Вход:

1
1

Ответ:

0

Во втором тестовом примере есть следующие способы разделения:
{ [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] }

Оценивание:

Данная задача содержит четыре подзадачи:
$1 \le N \le 50$. Оценивается в $11$ баллов.
$1 \le N \le 500$. Оценивается в $21$ балл.
$1 \le N \le 2000$. Оценивается в $31$ балл.
$1 \le N \le 5000$. Оценивается в $37$ баллов. ( Темірұлан Мусаев )