Problem1981--The Dream of Luo Dashen

1981: The Dream of Luo Dashen

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

Actually, Luo Dashen has a very great dream which is becoming a singer. In order to realize this dream, he decides to hold a concert for his own. Now he is worried about the number of dancers. Nevertheless, he is preparing his songs. Hence, he asks the members of ACM team to help him.

Because Luo Dashen is very famous, many people want to help him. But in order to the overall effect, he has to abandon some of them. So Yao sister numbers them from 1 to N, and measures the height of each person. The height of the ith person is h[i]. Yao sister has to abandon some people for the whole effect and the category of height of the rest of the people is minimum. For example, the heights of five people  are 1, 1, 2, 2, 3 respectively. If Yao sister abandons a person, in order to achieve the result, he has to abandon the fifth person. Finally, it remains two kinds of heights 1 and 2.

Input

Input contains multiple test cases.

For each test case, the first line contains an integer N (0<=N<100000). The second line includes N integers separated by a space. These integers indicate people’s heights h[i] (0<h[i]<=N). The third line contains an integer K that is the number of people after Yao sister’s abandoning.

The last test case is followed by a line containing a zero.

Output

Output your answer which represents the number of the category of the height of the rest of people in one line.

Sample Input Copy

5
1 1 2 2 3
4
5
2 3 1 2 1
4
0

Sample Output Copy

2
2

Source/Category