408694: GYM103264 C Счастливые дни

Широко известна легенда про ханойские башни — про монахов в ханойском храме, перекладывающих диски по определенным правилам до конца света.

Намного менее известна другая легенда — что в этом же храме есть $$$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 баллов.

4
1 3 2 4
3

1

Занумеруем диски в примере по порядку от меньшего к большему.

В день сотворения мира диски лежали в следующем порядке: $$$1, 2, 3, 4$$$.

На следующий день (день номер 1) диски лежали в следующем порядке: $$$1, 3, 2, 4$$$.

Во второй день — $$$1, 2, 3, 4$$$.

В третий день — $$$1, 3, 2, 4$$$.

В третий день есть только одна пара дисков, лежащих в неправильном порядке — диски 3 и 2, поэтому счастливость третьего дня равна 1.