TLL237 - Addicted

Jhon is compulsive saver, he keeps a number "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 least amount of money. If that number is two (2) he deposits the penny on the next piggy bank with the least 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 least amount of money once the sequence is over.

If more than two have the least 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 ≤ 105

s is the sequence with 1's and 2's, 1 ≤ size(s) ≤ 105

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

Added by:tille
Date:2012-08-10
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:tille

hide comments
2020-02-06 04:50:46
Nice problem to test efficiency of a certain idiom I never had opportunity to use before.
2012-09-11 05:08:55 Naman
O (n*size of string) won't pass
2012-08-13 17:44:13 Ehor Nechiporenko
What about the version with
n <= 10^7
size(s) <= 10^7
;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.