#agc013f. [agc013_f]Two Faced Cards
[agc013_f]Two Faced Cards
Problem Statement
There are cards. The two sides of each of these cards are distinguishable. The -th of these cards has an integer printed on the front side, and another integer printed on the back side. We will call the deck of these cards . There are also cards of another kind. The -th of these cards has an integer printed on the front side, and nothing is printed on the back side. We will call this another deck of cards .
You will play rounds of a game. Each of these rounds is played independently. In the -th round, you are given a new card. The two sides of this card are distinguishable. It has an integer printed on the front side, and another integer printed on the back side. A new deck of cards is created by adding this card to . Then, you are asked to form pairs of cards, each consisting of one card from and one card from . Each card must belong to exactly one of the pairs. Additionally, for each card from , you need to specify which side to use. For each pair, the following condition must be met:
- (The integer printed on the used side of the card from ) (The integer printed on the card from )
If it is not possible to satisfy this condition regardless of how the pairs are formed and which sides are used, the score for the round will be . Otherwise, the score for the round will be the count of the cards from whose front side is used.
Find the maximum possible score for each round.
Constraints
- All input values are integers.
Input
Input is given from Standard Input in the following format:
Output
For each round, print the maximum possible score in its own line.
Sample Input 1
Sample Output 1
For example, in the third round, the cards in are . The score of can be obtained by using front, back, back and front sides of them, and pair them with the fourth, third, first and second cards in , respectively. It is not possible to obtain a score of or greater, and thus the answer is .