Темирулан против Пернехана
Темирулан против Пернехана
Темирулану и Пернехану подарили последовательность A из n (1 ≤ n ≤ 5000) целых положительных чисел. Они договорились поделить эту последовательность. Каждый из них должен взять некоторую не пустую последовательную часть последовательности, причем часть Темирулана должна начинаться раньше части Пернехана. Они хотят выглядеть уникально, поэтому они хотят чтобы не существовало ни одного числа, встречающегося в участке Темирулана и Пернехана одновременно. Айдос, наблюдавший за ними, заинтересовался, сколько существует различных способов сделать это. Помогите ему, напишите программу для количества способов.
Giriş verilənləri
Первая строка содержит целое число n. Следующая строка содержит n целых чисел A[i]
(1 ≤ A[i]
≤ n, 1 ≤ i ≤ n), разделенных пробелами.
Çıxış verilənləri
Выведите единственное число - ответ на задачу.
Nümunə
3 1 2 3
5
4 1 2 3 2
9
1 1
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] }