Toxel любит массивы. Перед поездкой в Paldea Serval подарил ему массив \(a\). Этот массив состоит из \(n\) попарно различных элементов.
Чтобы получить больше массивов, Toxel выполнил \(m\) операций с исходным массивом. \(i\)-й операцией он изменил \(p_{i}\)-й элемент \((i-1)\)-го массива на \(v_{i}\), в результате чего получился \(i\)-й массив (исходный массив \(a\) имеет номер \(0\)). Во время изменений Toxel гарантировал, что элементы каждого массива по-прежнему попарно различны после каждой операции.
Наконец, Toxel получил \(m+1\) массив и обозначил их как \(A_{0}=a, A_{1},\ldots,A_{m}\). Для каждой пары \((i,j)\) (\(0\le i<j\le m\)), Toxel определил её значение как количество различных элементов в конкатенации \(A_{i}\) и \(A_{j}\). Теперь Toxel задается вопросом, какова сумма значений для всех пар массивов? Пожалуйста, помогите ему вычислить ответ.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — сумму значений для всех пар массивов.
Примечание
В первом наборе входных данных массив изменяется следующим образом: \([1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]\).
Конкатенацией \(0\)-го массива \(1\)-го массива является \(\require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]\). Здесь есть \(4\) различных элемента.
Конкатенацией \(0\)-го массива и \(2\)-го массива является \(\require{cancel}[1,2,3,4,5,\cancel{3}]\). Здесь есть \(5\) различных элементов.
Конкатенацией \(1\)-го массива и \(2\)-го массива является \(\require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]\). Здесь есть \(4\) различных элемента.
Зачёркнутые элементы являются повторяющимися в массиве.
Таким образом, ответ равен \(4+5+4=13\).
Во втором наборе входных данных обратите внимание, что массив может оставаться без изменений после операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
|
13
1
705
|