n позиций, пронумерованных от 0 до n - 1, в рейтинги first и second (каждый массив — перестановка чисел от 0 до n - 1, первым идёт лучший).
Тройка различных позиций {x, y, z} **согласована**, если в обоих рейтингах они стоят в одном и том же порядке: например, x раньше y, а y раньше z — и в first, и в second.
Верните количество согласованных троек. Каждый набор из трёх позиций считается один раз.
Перебор всех троек — O(n³), а n бывает до 10⁵.first=[1, 0, 2, 3], second=[0, 1, 2, 3] → 2
В обоих рейтингах в одном порядке идут тройки (1, 2, 3) и (0, 2, 3). В тройках с 0 и 1 эти двое стоят в рейтингах по-разному.
first=[0, 1, 2], second=[0, 1, 2] → 1
Рейтинги совпадают, и единственная тройка подходит.
first=[3, 2, 1, 0], second=[0, 1, 2, 3] → 0
Второй рейтинг — первый наоборот, ни одна тройка не совпадает по порядку.
first и second — перестановки чисел от 0 до n - 1first=[1, 0, 2, 3], second=[0, 1, 2, 3]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 103 теста на сервере, включая скрытые.