In a land with developed democracy far, far away, presidential elections for the football
association are taking place. This land consists of
During the election campaign, candidates visited the counties and tried to gain their sympathies. After having met all the candidates, each county's football association determined the order in which they would cast their vote for each candidate.
For example, let's assume that there are four candidates in the election and that one
county's order is
Zdravko is a passionate football fan, and also a close friend of candidate with label
He also wants to know what is the minimal number of candidates he must persuade to
revoke their candidacy in order for his friend, candidate
Zdravko is currently dealing with other problems, so he is hoping that you will answer these questions.
Input Specification
The first line of input contains the numbers
Output Specification
You must output the answers to the questions from the task, each in its own line.
Scoring
The output must consist of two non-empty lines, each containing a single integer. The
correct answer to each of the questions is worth
Sample Input 1
3 4 1
3 4 1 2
4 2 3 1
3 4 2 1
Sample Output 1
3
3
Explanation for Sample Output 1
The land where the elections are being held consists of 3 counties, and there are 4 candidates for the
president of the association. If none of the candidates revoke their candidacy, candidate
Sample Input 2
4 1 1
1
1
1
1
Sample Output 2
1
0
Explanation for Sample Output 2
There is only one candidate, Zdravko's friend, so they will surely win.
Sample Input 3
4 4 4
2 3 1 4
2 3 1 4
1 3 2 4
4 3 2 1
Sample Output 3
2
3
Comments