B. Новый год и восходящая последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность $$$a = [a_1, a_2, \ldots, a_l]$$$ длиной $$$l$$$ имеет восход, если существует пара таких индексов $$$(i, j)$$$, что $$$1 \le i < j \le l$$$ и $$$a_i < a_j$$$. Например, последовательность $$$[0, 2, 0, 2, 0]$$$ имеет восход из-за пары индексов $$$(1, 4)$$$, но последовательность $$$[4, 3, 3, 3, 1]$$$ не имеет восхода.

Назовем конкатенацией двух последовательностей $$$p$$$ и $$$q$$$ такую последовательность, которая получится при последовательной записи сначала $$$p$$$, затем $$$q$$$ друг за другом, не меняя порядок элементов в них. Например, конкатенация последовательностей $$$[0, 2, 0, 2, 0]$$$ и $$$[4, 3, 3, 3, 1]$$$ равна последовательности $$$[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$$$. Конкатенация последовательностей $$$p$$$ и $$$q$$$ обозначается как $$$p+q$$$.

Кенгун считает, что последовательность с восходом приносит удачу. Поэтому он хочет сделать много таких последовательностей на новый год. У Кенгун есть $$$n$$$ последовательностей $$$s_1, s_2, \ldots, s_n$$$, которые могут иметь разную длину.

Кенгун рассмотрит $$$n^2$$$ всевозможных пар последовательностей $$$s_x$$$ и $$$s_y$$$ ($$$1 \le x, y \le n$$$) и проверит содержит ли конкатенация $$$s_x + s_y$$$ восход или нет. Обратите внимание, что порядок выбора последовательностей в пару имеет значение. Кроме того, он может выбирать последовательность в пару к самой себе.

Пожалуйста, посчитайте количество пар последовательностей ($$$x, y$$$) для заданного набора $$$s_1, s_2, \ldots, s_n$$$, конкатенация $$$s_x + s_y$$$ которых имеет восход.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$), обозначающее количество последовательностей.

В каждой из следующих $$$n$$$ строк записано целое число $$$l_i$$$ ($$$1 \le l_i$$$), обозначающее длину $$$s_i$$$, после которой записано $$$l_i$$$ целых чисел $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$$$ ($$$0 \le s_{i, j} \le 10^6$$$), обозначающие последовательность $$$s_i$$$.

Гарантируется, что сумма всех $$$l_i$$$ не превосходит $$$100\,000$$$.

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

Выведите одно целое число, количество пар последовательностей, конкатенация которых имеет восход.

Примеры
Входные данные
5
1 1
1 1
1 2
1 4
1 3
Выходные данные
9
Входные данные
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6
Выходные данные
7
Входные данные
10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100
Выходные данные
72
Примечание

В первом примере, следующие $$$9$$$ последовательностей имеют восход: $$$[1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]$$$. Одинаковые по содержимому последовательности учитываются столько раз, сколько раз они встречаются как результат конкатенации.