SDE - 1

You live in a Ninja town which is in the form of a N * M grid. In this town, people travel from one place to another by jumping over the buildings which are present in each cell of the grid. It is Christmas eve, and Santa wants to give gifts and chocolates to the kids who live in the building which is present at the cell (N - 1, M - 1). Initially, Santa is present on cell (0, 0). Since Santa is in a hurry, help him find a path from starting point to the endpoint with the least amount of time.

The Santa may go only from one building to any of its adjacent buildings which is present either to the right or to the bottom or bottom right cell i.e. if the current position is (x, y), he may go to (x + 1, y + 1) or (x + 1, y) or (x, y + 1) given that the new coordinates are in the grid. The time taken to reach from one building to another is equal to the absolute difference between the heights of buildings.

Note:

1. The heights of the buildings are positive.
2. Santa starts from the cell (0, 0) and he has to reach the building (N - 1, M - 1).
3. Santa cannot leave the grid at any point of time.

Ninja and his friend are working on an assignment that contains ‘N’ tasks. Each task has a complexity ‘C[i]’.

Ninja wants to assign ‘B’ number of tasks to his friend and ‘A’ number of tasks to himself. Given that he can only assign tasks with complexity greater than or equal to 'X' to himself and tasks with complexity less than 'X' to his friend.

So help Ninja to find how many ways are there to choose ‘X’ such that Ninja gets ‘A’ and his friend gets ‘B’ number of tasks.

Note :

The complexity of each task is pairwise distinct.

For example :

N a b
5 3 2
C: 5 19 2 62 1
Here ‘X’ can be 2,3,4 as 3 tasks have greater complexity that will be assigned to Ninja and the remaining two will be assigned to NInja’s friend.
So the answer is 3.