В этот приятный весенний полдень фермер Джон решил поспать k минут, пока его n коров обсуждают подробности структуры linking-cutting, построенной на кактусах в их стойлах. Коровы пронумерованы от 1 до n, и корова с номером i изначально находится в стойле с номером i. Однако Элси порядком надоело жить в тени славы Бесси, поэтому она организовала тайное общество Бешеных Братьев Беспорядка и планирует нарушить размеренную жизнь на пастбище. Пока фермер Джон будет спать, Элси и её сообщники будут каждую минуту выбирать не более чем одну пару коров и менять их местами.
Элси хотела бы знать, какой максимальный хаос они могут навести за k минут. Обозначим как pi номер коровы расположенной в i-м стойле. Тогда значением хаоса данного расположения коров называется количество таких пар (i, j), что i < j и pi > pj.
Выходные данные
Выведите единственное целое число — максимальный уровень хаоса в коровнике, которого можно достигнуть, сделав не более k обменов двух коров местами.
Примечание
В первом примере Бешеные Братья Беспорядка могут за первую минуту поменять местами коров в стойлах 1 и 5, а за вторую минуту поменять местами коров в стойлах 2 и 4. Таким образом, коровы будут стоять с обратном порядке, и значение хаоса будет равно 10.
Во втором примере есть только одна корова, поэтому уровень хаоса равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
|
10
|
|
2
|
1 10
|
0
|