Вам задан массив, состоящий из \(n\) целых чисел \(a_1, a_2, \dots , a_n\) и целое число \(x\). Гарантируется, что для любого \(i\) выполняется \(1 \le a_i \le x\).
Функция \(f(l, r)\) удаляет все числа из массива \(a\), для которых выполняется \(l \le a_i \le r\), и возвращает полученный массив. Например, если \(a = [4, 1, 1, 4, 5, 2, 4, 3]\), тогда \(f(2, 4) = [1, 1, 5]\).
Вам нужно посчитать количество пар \((l, r)\), таких, что \(1 \le l \le r \le x\) и массив \(f(l, r)\) отсортирован в порядке неубывания. Обратите внимание, что пустой массив тоже считается отсортированным.
Выходные данные
Выведите количество пар \(1 \le l \le r \le x\), таких, что массив \(f(l, r)\) отсортирован в порядке неубывания.
Примечание
В первом тестовом примере подходящие пары — это \((1, 1)\), \((1, 2)\), \((1, 3)\) и \((2, 3)\).
Во втором тестовом примере подходящие пары — это \((1, 3)\), \((1, 4)\), \((2, 3)\), \((2, 4)\), \((3, 3)\) и \((3, 4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
2 3 1
|
4
|
|
2
|
7 4
1 3 1 2 2 4 3
|
6
|