Problem Statement

There are four balls, and the color of the i-th ball is A_i.

Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

Constraints

• Each of A_1, A_2, A_3, A_4 is an integer between 1 and 4, inclusive.

Sample Input 1

2 1 2 1

Sample Output 1

2

The first and third balls both have color 2, so you can perform the operation to discard the first and third balls together.

Next, the second and fourth balls both have color 1, so you can perform the operation to discard the second and fourth balls together.

Hence, you can perform a total of two operations.

Sample Input 2

4 4 4 1

Sample Output 2

1

Sample Input 3

1 2 3 4

Sample Output 3

0

There are cases where you cannot perform the operation even once.

Problem Statement

You are given an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

• 0 \leq N \leq 9999
• N is an integer.

Sample Input 1

321

Sample Output 1

0321

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

7777

Sample Output 2

7777

Sample Input 3

1

Sample Output 3

0001

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Here, A_1, A_2, \ldots, A_N are all distinct.

Which element in A is the second largest?

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• A_1, A_2, \ldots, A_N are all distinct.
• All input values are integers.

Sample Input 1

4
8 2 5 1

Sample Output 1

3

The second largest element in A is A_3, so print 3.

Sample Input 2

8
1 2 3 4 5 10 9 11

Sample Output 2

6

Problem Statement

There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.

Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.

Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Constraints

• -10^{18}\leq A \leq 10^{18}
• 1\leq M \leq 10^9
• -10^{18}\leq L\leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

5 3 -1 6

Sample Output 1

3

Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.

Sample Input 2

-2 2 1 1

Sample Output 2

0

Sometimes, Takahashi and Aoki are standing at the same point.

Sample Input 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

Sample Output 3

273142010859

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

4
2 3 4 3 4 1 3 1 1 4 2 2

Sample Output 3

3 4 1 2