P6140 [USACO07NOV] Best Cow Line S

*This problem has the same meaning as the [problem with the same name in the December 2007 Monthly Contest (Gold)](/problem/P2870). The only difference is the Constraints.*

Farmer John plans to lead $N$ cows ($1 \leq N \leq 2\,000$) to take part in the annual "All-American Farmers Grand Prix". In this contest, each participant must line up his cows in a single row, and then lead them past the judges one by one. This year, the contest committee adopted a new registration rule: take the first letter of each cow’s name and arrange them into a sequence according to their order in the line. Then sort all teams’ sequences in increasing lexicographical order to determine the appearance order. Because FJ is busy, he wants to appear as early as possible, so he decides to rearrange the line. His method is as follows: each time, he leads one cow from either the front or the back of the original line, and places her at the end of a new line. Repeat this until all cows have been inserted into the new line. Now please help FJ compute the lexicographically smallest sequence that can be produced using the method above.

The first line contains an integer $N$. The next $N$ lines each contain one uppercase letter, representing the initial line.

Output a string of length $N$, representing the smallest possible lexicographical sequence. Print a newline after every $80$ letters.

Translated by ChatGPT 5