Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#0000E4

Tournament

After the exciting swimming race at the Summer Olympics in Bejing <a href="http://graphics8.nytimes.com/images/blogs/olympics/phelpscavic533.jpg">(photo finish)</a>, the judges decided to change the rules a little bit. From now and on, every swimmer will be assigned a number representing its strength. Then they play single elimination rounds in pairs <a href="http://en.wikipedia.org/wiki/Single-elimination_tournament">(info)</a>. Every time a swimmer swims against another swimmer with lower strength, he wins. You are given a list of swimmers with their strengths. Obviously, the number of wins of each player will depend on his opponents (the way the elimination rounds are setup). You have to find the minimal and the maximal possible number of wins that the i-th player can have.


InputFrom the first line of the standard input read two numbers n - number of swimmers, and i - the number of the swimmer we are interested in (the first swimmer has a number 0, and the last one has a number n-1). The next n lines contain the n numbers representing the strength of each of the swimmers. n is less than 1 000 001, and is always a power of 2. None of two swimmers will have the same strength, and all the strengths are less than 2^31.

Output To the standard output write two numbers: the minimal and the maximal number of wins that the i-th player can have.


Input:
8 4
5
7
1
6
4
2
3
8
Output:
0 2
Explanation:
Minimum is 0 - the 4th swimmer have strength of 4. If it swims against the 3th swimmer (strength 6) in the first round, he will lose, and hence have 0 wins.
Maximum is 2. The 4th swimmer could have raced against the 2nd player in the first round, and against the winner of the 5th and 6th swimmers in the second round. Hence it will win two rounds. After that only the swimmers with higher strengths are left, so the 4th swimmer will lose the 3rd race.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.