Второй тур подходил к концу, и Сарай уже думает сразу после тура пойти позаниматься в качалочку. Одно из любимых упражнений Сарая — это поднятие штанги. Штанга представляет из себя гриф с дисками, которые расположены в определённом порядке. То есть штангу можно представить массив $$$a$$$ размером $$$n$$$, где $$$a_i$$$ — вес $$$i$$$-го диска. Гарантируется, что все диски имеют различный вес.

Но чтобы нормально позаниматься, надо, чтобы штанга была сбалансирована. Штанга $$$k$$$-сбалансирована, если выполняется условие: $$$a_n = k$$$, $$$a_{n-1} = k-1$$$, $$$...$$$, $$$a_{n-k+1} = 1$$$. Чтобы привести штангу к $$$k$$$-сбалансированному состоянию, Сарай может поменять местами два соседних диска, но поскольку они тяжелые, надо выполнить это за минимальное количество действий.

Поскольку Сарай хочет попробовать разные способы балансировки, чтобы найти для себя идеальный, вы должны найти минимальное количество действий для всех $$$q$$$ запросов $$$k$$$-балансировок, которые интересны ему.