Задача №114293. Счастливые дни
Широко известна легенда про ханойские башни — про монахов в ханойском храме, перекладывающих диски по определенным правилам до конца света.
Намного менее известна другая легенда — что в этом же храме есть \(N\) стержней, занумерованных от 1 до \(N\). Рядом с каждым стержнем написано одно число от 1 до \(N\), все числа различны. На каждом стержне лежит один золотой диск. Все диски разных размеров, и при сотворении мира диски лежали по порядку: самый маленький диск на первом стержне, и т.д., самый большой — на последнем.
Каждую ночь, в полночь, монахи проводят следующую операцию. Они снимают все диски со стержней, после чего перекладывают их в соответствии с числами, написанными около стержней: диск, лежавший на первом стержне, перекладывается на стержень с номером, равным числу, написанному около первого стержня; диск, лежавший на втором стержне — на стержень с номером, равным числу, написанному около второго стержня, и так далее. Формально: если рядом с \(i\)-м стержнем написано число \(a_i\), то диск, лежавший на \(i\)-м стержне, перекладывается на стержень с номером \(a_i\).
Получившееся расположение дисков определяет счастливость наступившего дня. Счастливость будет равна количеству пар дисков \(a, b\), лежащих в «неправильном порядке», т.е. таких, что диск \(a\) больше диска \(b\), но лежит на стержне с меньшим номером.
Напишите программу, которая по порядковому номеру дня с сотворения мира определяет его счастливость.
В первой строке записано натуральное число \(n\) \((1 \leq n \leq 100\,000)\) — количество стержней и дисков.
Во второй строке записано \(n\) натуральных чисел \(a_i\) \((1 \leq a_i \leq n)\) — числа, написанные рядом со стержнями. Гарантируется, что все эти числа различны.
В третьей строке записано одно неотрицательное целое число \(S\) — номер дня с сотворения мира. День, когда был сотворен мир, считается днем номер ноль. Гарантируется, что в записи числа \(S\) содержится не более \(10^5\) десятичных цифр.
В единственной строке выведите счастливость \(S\)-го дня.
Решения, работающие для \(n \cdot S \leq 10^8\), будут набирать не менее 30 баллов.
Решения, работающие для \(n \cdot S \leq 10^8\) и \(n \leq 10^4\) будут набирать не менее 20 баллов.
Занумеруем диски в примере по порядку от меньшего к большему.
В день сотворения мира диски лежали в следующем порядке: \(1, 2, 3, 4\).
На следующий день (день номер 1) диски лежали в следующем порядке: \(1, 3, 2, 4\).
Во второй день — \(1, 2, 3, 4\).
В третий день — \(1, 3, 2, 4\).
В третий день есть только одна пара дисков, лежащих в неправильном порядке — диски 3 и 2, поэтому счастливость третьего дня равна 1.
4 1 3 2 4 3
1