35412번 - 스택과 팰린드롬

길이 $N$의 문자열 $S$와 비어 있는 문자열 $R$이 주어질 때 다음 과정을 $S$가 비어있을 때까지 반복하여 적용한 뒤의 $R$을 구하여라.

1. $S$의 맨 앞 글자를 삭제한 뒤 삭제한 글자를 $R$의 맨 뒤에 추가한다.
2. 이후 $R$에 길이 $2$ 이상의 팰린드롬 부분 문자열이 있다면 그중 가장 긴 문자열을 $R$에서 삭제한다. 만약 가장 긴 팰린드롬 부분 문자열이 여럿 있다면 그중 가장 앞에 있는 문자열을 삭제한다.
3. 2번 단계를 $R$에 길이 $2$ 이상의 팰린드롬 부분 문자열이 없을 때까지 반복한다.

첫 번째 줄에 문자열 $S$의 길이 $N$이 주어진다. $(1 \le N \le 5\times 10^5)$

두 번째 줄에 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다.

첫 번째 줄에 문제에서 설명한 과정을 모두 적용한 뒤의 $R$을 출력한다. 단, 모든 과정을 적용한 뒤 $R$이 비어있다면 -1을 대신 출력한다.

문자열 $A$가 문자열 $B$의 연속된 부분으로 나타난다면 $A$를 $B$의 부분 문자열이라고 한다. 예로 di, m, dimi는 dimi의 부분 문자열이지만 a, ii, mid는 dimi의 부분 문자열이 아니다.

문자열 $A$를 앞에서부터 읽어도 뒤에서부터 읽어도 같다면 $A$를 팰린드롬이라고 한다. 예로 a, sees, racecar는 팰린드롬이지만 cab, dimi, palindrome은 팰린드롬이 아니다.