Pretty numbers

Time limit1sMemory limit1024 MB

Summary

Given a sequence of N digits, find the largest pretty number formed by consecutive elements of the sequence.

Level: Medium6 of 10
Topics: String, String matching, Implementation
Solved: No attempts yet

Problem

A pretty number is built from blocks of repeated digits that all have the same length. If a number starts with digit X repeated k times, the next block is a different digit Y repeated k times. After that comes a block of a digit different from Y (it may be X again), also repeated k times, and so on. For example, 112233, 111222111, 123, and 1 are pretty, while 11223, 11122111, and 1233 are not.

Given a sequence of N digits, write a program prettynum that finds the largest pretty number whose digits are consecutive elements of the given sequence.

Input

The first line contains the integer N. The second line contains N digits separated by spaces, which form the sequence in which the largest pretty number is searched for.

Output

Print the largest pretty number whose digits are consecutive elements of the given sequence, on a single line.

Constraints

$3 \le N \le 1000000$

Examples2

Example 1
Input
```
8
1 1 1 0 0 2 2 2
```
Expected output
```
110022
```
Example 2
Input
```
7
1 1 0 0 0 2 2
```
Expected output
```
1100
```