← 返回题目列表

AtCoder · icpc2016autumn_a

A. 最佳搭配

中文机器翻译题面 查看原题

问题陈述

您在东京的一家全球游戏公司担任工程师。 该公司每年夏天都会为公司全体员工举办一年一度的活动。今年的活动将在东京举行。 您将与组织工作人员一起参加活动。 你被分配去计划一个所有参与者同时玩的娱乐游戏。

在你想出了各种想法后,你设计了如下的游戏规则。

  • 在游戏开始前,每个玩家都会获得一个正整数。
  • 在这个游戏中,每个玩家都尝试与另一个玩家配对,并通过比较两个整数的乘积来相互竞争。
  • 每个玩家在游戏结束前可以多次更换搭档,但不能同时拥有两个或更多搭档。
  • 游戏结束时,乘积最大的一对获胜。

此外,对于给定的整数,必须满足下一个条件才能配对。

  • 将一对中的两个整数的乘积视为字符串所获得的数字序列必须是递增的并且从左到右连续。 例如,$2$、$23$ 和 $56789$ 满足此条件,但 $21$、$334$、$135$ 或 $89012$ 则不满足。

按照上述规则设置,您注意到根据情况,可能会有多对拥有相同产品的获胜者。但是,当给定一组整数时,您可以找出两个整数的最大乘积是多少。

你的任务是,给定一组分配给玩家的不同整数,计算两个整数的最大可能乘积,满足上述游戏规则。


输入

输入由单个测试用例组成,格式如下。

$N$
$a_{1} \ a_{2} \ \点 \ a_{N}$

第一行包含一个正整数$N$,表示游戏的玩家数量。 $N$ 是介于 $1$ 和 $1,000$ 之间的整数。 第二行有 $N$ 个正整数,表示给予玩家的数字。 对于 $i =1, 2, \ldots, N-1$,$a_i$ 和 $a_{i+1}$ 之间有一个空格。 $a_i$ 介于 $1$ 和 $10,000$ 之间,$i =1,2, \ldots, N$, 如果 $i \ne j$,则 $a_i \ne a_j$。

输出

打印满足配对条件的两个整数的最大可能乘积。 如果任意两个玩家无法配对,则打印 $-1$。



示例输入 1

2
1 2

样本输入 1 的输出

2

示例输入 2

3
3 22 115

样本输入 2 的输出

345

示例输入 3

2
1 11

样本输入 3 的输出

-1

示例输入 4

2
5 27

样本输入 4 的输出

-1

示例输入 5

2
17 53

样本输入 5 的输出

-1

示例输入 6

10
53 43 36 96 99 2 27 86 93 23

样本输入 6 的输出

3456