Longest Double Ballot Substring

Bytea went to a salad bar. Along the bar, there are n fruits arranged in a line. Each fruit is either an apple or an orange, represented by the characters 'j' and 'p' respectively.

Bytea may choose any contiguous part (substring) of the fruit line for her salad. The fruits in the chosen substring will be added one-by-one to the salad, either from left‐to‐right or from right‐to‐left. Because Bytea loves oranges, she requires that during the salad‐making process, the number of oranges (i.e. the number of character p) is never less than the number of apples (character j). In other words, if we assign a value of +1 for an orange (p) and −1 for an apple (j), then while processing the chosen substring sequentially (in either direction) the cumulative sum should always be nonnegative.

Formally, for a substring S of the input string, let each character be mapped as follows:

[ \text{value}(c)=\begin{cases}+1,&\text{if }c=p,\-1,&\text{if }c=j. \end{cases} ]

Let F(i) be the cumulative sum of S up to position i (i.e. the sum of mapped values of the first i characters), and let D be the total sum of S. Then S is valid if and only if for every prefix (when reading left-to-right) we have

[ F(i)\ge0, \quad 1\le i\le |S|, \quad \text{and} \quad F(i)\le D, \quad 1\le i\le |S|. ]

Your task is to find one longest contiguous substring of the given string that satisfies these conditions. If there is more than one answer, any one is acceptable. If no valid substring exists, output an empty string.

inputFormat

The input consists of two lines:

• The first line contains a single integer n, the length of the string.
• The second line contains a string of length n containing only the characters p and j.

outputFormat

Output the longest contiguous substring satisfying the double ballot condition described above. If there is no valid substring, output an empty string.

sample

3
pjp

pjp