Jhon is compulsive saver, he keeps and amount "n" of piggy banks locked in his room.

He has a list which he wrote with a sequence of 1's and 2's that indicate the way that Jhon will deposit his money on the piggy banks. Every time Jhon gets a penny he rushes to his room and picks the 2 piggy banks who have the least amount of money, then he looks at the next number on the sequence. If that number is one (1) he deposits the penny on the piggy bank with the lesser amount of money. If that number is two (2) he deposits the penny on the next piggy bank with the lesser amount of money.

Your task is to write a program to help Jhon to determine what is the amount in the 2 piggy banks with less money once the sequence is over

If more than two have the lowest amount of money choose those with lowest indexes.

You can assume that n <= s.

Input

The input is a single data set.

n is the number of piggy banks, 2 <= n <= 10^5

s is the sequence with 1's and 2's, 1 <= size(s) <= 10^5

Output

A line containing what is the amount in the 2 piggy banks with least money once the sequence is over, sorted from lowest to highest.

Example

Input:
3
111112

Output:
1 2