Последовательность \(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\) которых имеет восход.
Примечание
В первом примере, следующие \(9\) последовательностей имеют восход: \([1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]\). Одинаковые по содержимому последовательности учитываются столько раз, сколько раз они встречаются как результат конкатенации.