Problem Statement

There are a total of A + B cats and dogs. Among them, A are known to be cats, but the remaining B are not known to be either cats or dogs.

Determine if it is possible that there are exactly X cats among these A + B animals.

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• 1 \leq X \leq 200
• All values in input are integers.

Sample Input 1

3 5 4

Sample Output 1

YES

If there are one cat and four dogs among the B = 5 animals, there are X = 4 cats in total.

Sample Input 2

2 2 6

Sample Output 2

NO

Even if all of the B = 2 animals are cats, there are less than X = 6 cats in total.

Sample Input 3

5 3 2

Sample Output 3

NO

Even if all of the B = 3 animals are dogs, there are more than X = 2 cats in total.

Problem Statement

There are N + 1 squares arranged in a row, numbered 0, 1, ..., N from left to right.

Initially, you are in Square X. You can freely travel between adjacent squares. Your goal is to reach Square 0 or Square N. However, for each i = 1, 2, ..., M, there is a toll gate in Square A_i, and traveling to Square A_i incurs a cost of 1. It is guaranteed that there is no toll gate in Square 0, Square X and Square N.

Find the minimum cost incurred before reaching the goal.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq X \leq N - 1
• 1 \leq A_1 < A_2 < ... < A_M \leq N
• A_i \neq X
• All values in input are integers.

Sample Input 1

5 3 3
1 2 4

Sample Output 1

1

The optimal solution is as follows:

• First, travel from Square 3 to Square 4. Here, there is a toll gate in Square 4, so the cost of 1 is incurred.
• Then, travel from Square 4 to Square 5. This time, no cost is incurred.
• Now, we are in Square 5 and we have reached the goal.

In this case, the total cost incurred is 1.

Sample Input 2

7 3 2
4 5 6

Sample Output 2

0

We may be able to reach the goal at no cost.

Sample Input 3

10 7 5
1 2 3 4 6 8 9

Sample Output 3

3

Problem Statement

When l is an odd number, the median of l numbers a_1, a_2, ..., a_l is the (\frac{l+1}{2})-th largest value among a_1, a_2, ..., a_l.

You are given N numbers X_1, X_2, ..., X_N, where N is an even number. For each i = 1, 2, ..., N, let the median of X_1, X_2, ..., X_N excluding X_i, that is, the median of X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N be B_i.

Find B_i for each i = 1, 2, ..., N.

Constraints

• 2 \leq N \leq 200000
• N is even.
• 1 \leq X_i \leq 10^9
• All values in input are integers.

Sample Input 1

4
2 4 4 3

Sample Output 1

4
3
3
4

• Since the median of X_2, X_3, X_4 is 4, B_1 = 4.
• Since the median of X_1, X_3, X_4 is 3, B_2 = 3.
• Since the median of X_1, X_2, X_4 is 3, B_3 = 3.
• Since the median of X_1, X_2, X_3 is 4, B_4 = 4.

Sample Input 2

2
1 2

Sample Output 2

2
1

Sample Input 3

6
5 5 4 4 3 3

Sample Output 3

4
4
4
4
4
4

Problem Statement

Let {\rm comb}(n,r) be the number of ways to choose r objects from among n objects, disregarding order. From n non-negative integers a_1, a_2, ..., a_n, select two numbers a_i > a_j so that {\rm comb}(a_i,a_j) is maximized. If there are multiple pairs that maximize the value, any of them is accepted.

Constraints

• 2 \leq n \leq 10^5
• 0 \leq a_i \leq 10^9
• a_1,a_2,...,a_n are pairwise distinct.
• All values in input are integers.

Sample Input 1

5
6 9 4 2 11

Sample Output 1

11 6

\rm{comb}(a_i,a_j) for each possible selection is as follows:

• \rm{comb}(4,2)=6
• \rm{comb}(6,2)=15
• \rm{comb}(6,4)=15
• \rm{comb}(9,2)=36
• \rm{comb}(9,4)=126
• \rm{comb}(9,6)=84
• \rm{comb}(11,2)=55
• \rm{comb}(11,4)=330
• \rm{comb}(11,6)=462
• \rm{comb}(11,9)=55

Thus, we should print 11 and 6.

Sample Input 2

2
100 0

Sample Output 2

100 0