Doubletrouble
The legendary wizzard Merlin is having fun in his lab. He has N magical potions (labeled 1, 2, ..., N)
arranged on a single line in a given order. He wants to rearrange them in ascending order. The potions
will be moved one at a time. The first potion moved will be the the one labelled with 1, then the potion
labelled by 2, and so on.
Of course, in order to solve the problem Merlin will use magic. Each potion can be moved using one or
more spells, passing through one or more intermediate positions. Moving a potion from position I to
position J, the spell will consume (I-J)2 energy units. For example, if there are 7 potions ordered 1,7,3,4,5,2,6 and Merlin moves the potion (labelled 2) from the sixth position to the second
position then the new arrangement will be 1,2,7,3,4,5,6 with (6-2)2 units of energy consumed.
Before the fun began, Merlin has established two criteria:
1. He doesn't want to be too tired at the end of the day, so he's not willing to consume more than E units of energy.
2. He also gets bored quickly, therefore he wants to solve the problem with a minimum number of spells.
Calculate the minimum number of spells Merlin can use to solve the problem.
Input
The input contains in the first line two positive integers N (1 ≤ N ≤ 105) and E (1 ≤ E ≤ 1015) separated by space and in the second line N positive integers separated by space, the K-th integer being the label of the potion from K-th position, 1 ≤ K ≤ N.
Output
The output will contain a single integer, the minimum number of spells used by Merlin, or -1 if there isn’t a solution.
Constraints
Time limit: 1 second
Memory limit: 128 megabytes
Examples
input 5 6 2 3 5 1 4 | output 3 |
Explanation for the first test:
2 3 5 1 4 --> 2 3 1 5 4 --> 1 2 3 5 4
1 2 3 5 4 --> 1 2 3 4 5
A minimum of three spells were used. Using the first two spells, with 12 and 22
units of energy, the potion 1 was moved to the first position. Using the third spell, with 12
units of energy, the potion 4 was moved to the fourth position. The total energy consumed is
12 + 22 + 12 = 6.