perm длины n — перестановка чисел от 1 до n.
Четвёрку индексов i < j < k < l назовём **четвёркой с перескоком**, если
perm[i] < perm[k] < perm[j] < perm[l].
Иначе говоря, значения растут, только средняя пара идёт «не в том» порядке: perm[j] больше, чем perm[k].
Верните количество таких четвёрок.
Перебор всех четвёрок — O(n⁴), при n до 4000 нужно решение за O(n²).perm=[2, 4, 3, 5, 1] → 1
Подходит четвёрка индексов (0, 1, 2, 3): значения 2, 4, 3, 5, и действительно 2 < 3 < 4 < 5.
perm=[1, 4, 2, 3, 5] → 2
Подходят (0, 1, 2, 4) — значения 1, 4, 2, 5 — и (0, 1, 3, 4) — значения 1, 4, 3, 5.
perm=[1, 2, 3, 4] → 0
Массив возрастает, второй элемент четвёрки никогда не больше третьего.
perm — перестановка чисел от 1 до nperm=[2, 4, 3, 5, 1]
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 87 тестов на сервере, включая скрытые.