eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3
1 2 3
Çıxış verilənləri #1
5
Giriş verilənləri #2
4
1 2 3 2
Çıxış verilənləri #2
9
Giriş verilənləri #3
1
1
Çıxış verilənləri #3
0

Qeyd

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

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

Mənbə 2015 Казахстан, 4-й этап Республиканской олимпиады по информатике, Уральск, 13-18 марта, Задача C