408694: GYM103264 C Счастливые дни
Description
Широко известна легенда про ханойские башни — про монахов в ханойском храме, перекладывающих диски по определенным правилам до конца света.
Намного менее известна другая легенда — что в этом же храме есть $$$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.