Climbing the Leaderboard

Alice is playing an arcade game and wants to climb to the top of the leaderboard. Can you help her track her ranking as she plays? The game uses Dense Ranking, so its leaderboard works like this:

• The player with the highest score is ranked number  on the leaderboard.
• Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

We want to determine Alice's rank as she progresses up the leaderboard. For example, the four players on the leaderboard have high scores of , , , and . Those players will have ranks , , , and , respectively. If Alice's scores are ,  and , her rankings after each game are ,  and .

You are given an array, , of monotonically decreasing leaderboard scores, and another array, , of Alice's scores for the game. You must print  integers. The  integer should indicate the current rank of alice after her  game.

Input Format

The first line contains an integer , the number of players on the leaderboard. 
The next line contains  space-separated integers , the leaderboard scores in decreasing order. 
The next line contains an integer, , denoting the number games Alice plays. 
The last line contains  space-separated integers , her game scores.

Constraints

•  for 
•  for 
• The existing leaderboard, , is in descending order.
• Alice's scores , are in ascending order.

Subtask

For  of the maximum score:

Output Format

Print  integers. The  integer should indicate the rank of alice after playing the  game.

Sample Input 1

7
100 100 50 40 40 20 10
4
5 25 50 120

Sample Output 1

6
4
2
1

Explanation 1

Alice starts playing with  players already on the leaderboard, which looks like this:

After Alice finishes game , her score is  and her ranking is :

After Alice finishes game , her score is  and her ranking is :

After Alice finishes game , her score is  and her ranking is tied with Caroline at :

After Alice finishes game , her score is  and her ranking is :

---

이 문제의 핵심은 다음 문장이다.

• The existing leaderboard, , is in descending order.
• Alice's scores , are in ascending order.

이 문장을 보고 alice의 점수와 leaderboard의 점수가 순서대로 정렬이 되어 있으니 당연히 leaderboard에서 한번 처리한 점수는 다시 계산할 필요가 없다고 생각했다. 그런데 그렇게 하려면 점수표 밑에서부터 계산을 해야 하는데, 계산을 하기 전에 leaderboard의 마지막 랭킹을 구해야 한다. 즉, 맨 꼴찌 Rank부터 밑에서 alice의 Rank를 찾고, 이미 지나간 점수는 다시 비교할 필요가 없어진다.

처음 문제를 보고 당연히 위의 방식을 생각했지만......일단 그냥 결과를 구하자는 막연한 생각으로 코딩을 했다.

그랬더니 역시나......Testcase를 넘어가지 못한다. 잘못 연산되거나 버그가 있는 것이 아니라 Timeout이 발생한다.

결국 이 문제는 제한된 시간안에 Rank를 모두 구해야 하는 것이 포인트 였던 것이다. 제한시간안에 Rank를 구하기 위해선 중복 비교를 하면 안되고 구해진 alice의 Rank 위로만 계산을 해야 한다.