Problem Statement

There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.

Find how many of the integers i=1,2,\ldots,N satisfy the following condition:

• There is exactly one person between the two people wearing clothes of color i.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq N
• Each integer from 1 through N appears exactly twice in A.
• All input values are integers.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

2

There are two values of i that satisfy the condition: 1 and 3.

In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Sample Input 2

2
1 1 2 2

Sample Output 2

0

There may be no i that satisfies the condition.

Sample Input 3

4
4 3 2 3 2 1 4 1

Sample Output 3

3

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

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:

• Choose two adjacent characters of S and swap them.

Find the minimum number of operations required to make S equal atcoder.

Constraints

• S is a string that is a permutation of atcoder

Sample Input 1

catredo

Sample Output 1

8

You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.

Sample Input 2

atcoder

Sample Output 2

0

In this case, the string S is already atcoder.

Sample Input 3

redocta

Sample Output 3

21