Best Matched Pair

Interview

Time limit2sMemory limit512 MB

Summary

Given up to 1000 distinct integers, find the largest product of two whose product's decimal digits form a consecutive increasing run like 123; print -1 if none exists.

Level: Medium4 of 10
Topics: Implementation, Brute force, Math, Sorting
Solved: No attempts yet

Problem

You work as an engineer at a game company in Tokyo. The company holds an event for its whole staff every summer. This year the event takes place in Tokyo, and you join it on the organizing side. Your assignment is to plan a recreation game that every participant plays at the same time.

After working through several ideas, you settled on the rules below.

Before the game starts, each player receives one positive integer.
Each player forms a pair with another player, and the pairs compete by comparing the products of their two integers.
A player may change partners any number of times before the game ends, but cannot have two or more partners at the same time.
When the game ends, the pair with the largest product wins.

The integers that were handed out must satisfy one more condition for a pair to form.

Reading the product of the two integers as a string, the digits must increase by 1 and run consecutively from left to right. For example, 2, 23, and 56789 satisfy the condition, while 21, 334, 135, and 89012 do not.

With these rules, several winning pairs with the same product can appear depending on the situation. Even so, once a set of integers is given, the largest product of two integers can be computed.

Given the set of distinct integers to hand out to the players, compute the largest product of two integers that satisfies the rules above.

Input

The input consists of a single test case in the following format.

N
a1 a2 ... aN

The first line contains a positive integer $N$ , the number of players. $N$ is an integer between $1$ and $1000$ . The second line contains $N$ positive integers, the numbers given to the players. For $i = 1, 2, \dots, N-1$ there is one space between $a_i$ and $a_{i+1}$ . For every $i$ , $1 \le a_i \le 10000$ , and if $i \ne j$ then $a_i \ne a_j$ .

Output

Print the largest product of two integers that satisfies the pairing condition. If no two players can form a pair, print $-1$ .

Examples6

Example 1
Input
```
2
1 2
```
Expected output
```
2
```
Example 2
Input
```
3
3 22 115
```
Expected output
```
345
```
Example 3
Input
```
2
1 11
```
Expected output
```
-1
```
Example 4
Input
```
2
5 27
```
Expected output
```
-1
```
Example 5
Input
```
2
17 53
```
Expected output
```
-1
```
Example 6
Input
```
10
53 43 36 96 99 2 27 86 93 23
```
Expected output
```
3456
```