Po managed to flatten all the tiles to ground level with the help of your program. As the last tile ground receded into a ground, there was a loud grinding noise. One of the walls of the room began to slide away, revealing another room. An entire row of tree logs planted vertically in the mud stood before Po, and on a few of these tree logs stood several villager bunnies. Upon inspecting one of the tree logs, Po found this message. "Outermost bunnies can hop to any position between two other bunnies. Only one bunny may hop at any time. Each hop causes all the tree logs to sink further into the ground. Bunnies love mud. Disaster awaits any bunny that hops off the tree logs before no bunny can hop."
Obviously, Po has to try and figure out how to ensure that the bunnies get as close to the mud as possible. Since each hop causes the tree logs to sink further into the ground, Po must figure out the maximum number of hops the bunnies can make. With a room full of vertical tree logs and noisy, squabbling rabbits, how is Po supposed to concentrate? Write a program to help him figure out the maximum number of hops possible.
Given the number of tree logs, the number of bunnies and their positions on the tree logs, figure out the maximum number of hops that the bunnies can make.
Input
There are two types of input: Type A and B.
For both type A and B inputs, the first line contains two integers, t and n. t represents the total number of tree logs, and n represents the number of bunnies.
The next line contains a character, 'A' or 'B', denoting whether the input is a type A or type B input respectively.
For type A inputs, the following line contains n integers p[0] ... p[n - 1], representing the positions of the tree logs that that the bunnies are standing on.
For type B inputs, the line contains the same n integers, but within strings which contain random characters (not including spaces).
For 50% of all test cases of both type A and B, n = 3.
For 100% of all test cases, 3 ≤ n ≤ 10 and n ≤ t ≤ 10000.
For 60% of all test cases, the input is a type A input, and the remaining 40% are type B inputs.
Output
Output one integer, representing the maximum number of hops that the bunnies can make.
Sample Input
10 3
A
1 4 7
Sample Output
2
Explanation
The first bunny can hop to position 6, and the last bunny can hop to position 5. After which, no other bunny can hop.
Sample Input
10 3
B
ab1kbs04'vbs[];[email protected]^(@&7wikdn
Explanation
There is a '1', '04', and '7' in the input.