String Construction

Interview

Time limit1sMemory limit128 MB

Summary

Repeatedly take the leftmost or rightmost character of S and append it to T; among all such T, output the lexicographically smallest, wrapping lines at 80 characters.

Level: Medium5 of 10
Topics: Greedy, String, Two pointers, Implementation
Solved: No attempts yet

Problem

A string $S$ of length $N$ is given.

Using the characters of $S$ , build a new string $T$ . Initially $T$ is empty. Repeat one of the following two operations until $S$ becomes empty:

Remove the first (leftmost) character of $S$ and append it to the end of $T$ .
Remove the last (rightmost) character of $S$ and append it to the end of $T$ .

Among all strings $T$ that can be produced this way, write a program that finds the lexicographically smallest one.

Input

The first line contains the length $N$ of the string $S$ . ( $1 \le N \le 2\,000$ )

Each of the next $N$ lines contains one character of $S$ , given in order.

Output

Print the lexicographically smallest string $T$ that can be produced. Insert a line break after every 80 characters.

Hint

Starting from $S =$ ACDBCB, one way to build $T$ proceeds as follows:

Step	Remaining $S$	$T$
1	ACDBCB	(empty)
2	CDBCB	A
3	CDBC	AB
4	CDB	ABC
5	CD	ABCB
6	D	ABCBC
7	(empty)	ABCBCD

Examples1

Example 1
Input
```
6
A
C
D
B
C
B
```
Expected output
```
ABCBCD
```