FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

  • Line 1: A single integer: N
  • Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

Output
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.

Sample Input
6
A
C
D
B
C
B
Sample Output
ABCBCD

题目大意：
输入一组字符，每次从第一个或最后一个输出，每次输出要满足可输出字符中最小的一个。

思路：
因为要保证每次输出均为最小，所以比较开头和末尾即可，但是存在开头和末尾相同的情况，这种情况下就应比较‘下一次’要比较的两字符，因此这里比较首字符和尾字符时，若相等就直接进入下一次循环，若不等就直接跳出循环输出（使用一个bool类型判断首尾，用int类型使用0，1判断也行）。

应注意没80个字符换行一次，因此需要记录输出次数并换行。

代码：

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
    int t;
    int num = 0;
    cin >> t;
    char v[2005];
    for (int i = 0; i < t; i++) {
        cin >> v[i];
    }
    int sic = 0;
    t--;
    while (sic <= t) {
        bool k = false;//判断大于或小于
        for (int i = 0; i <= t - sic; i++) {
            if (v[sic + i] < v[t - i]) {
                k = true;
                num++;
                break;
            }
            else if (v[sic + i] > v[t - i]) {
                k = false;
                num++;
                break;
            }
        }
        if (k)//输出首或尾
            cout << v[sic++];
        else
            cout << v[t--];
        if (num % 80 == 0)//换行
            cout << endl;
    }
    return 0;
}