I - /2 and *3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の正整数のみからなる数列 A=(A_1,A_2,\dots,A_N) が与えられます。
この数列に以下の操作を 0 回以上何度でも行ってよいとき、数列の項の最小値として達成可能な最大値を求めてください。

  • まず、数列の中から偶数である項を 1 つ選び、その項を 2 で割る。次に、数列の中から任意の項を 1 つ選び、その項を 3 倍する。

制約

  • 入力は全て整数
  • 1 \le N \le 10^5
  • 1 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

3
18 21 46

出力例 1

23

例えば、以下の操作を行うことで、項の最小値を 23 にすることができます。

  • はじめ、A=(18,21,46) である。
  • A_1 を 2 で割り、 A_1 を 3 倍する。この操作の後、数列は A=(27,21,46) となる。
  • A_3 を 2 で割り、 A_2 を 3 倍する。この操作の後、数列は A=(27,63,23) となる。

入力例 2

5
3 5 7 11 13

出力例 2

3

一度も操作が行えない場合もあります。

入力例 3

1
536870912

出力例 3

68630377364883

答えが 32 bit 符号付き整数型に収まらないこともあります。

Score : 6 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).
It is allowed to do the operation below any number of times, possibly zero. Find the largest value that can be taken by the smallest element of the sequence.

  • First, choose one element of the sequence that is an even number, and divide it by 2. Next, choose any one element, and multiply it by 3.

Constraints

  • All values in input are integers.
  • 1 \le N \le 10^5
  • 1 \le A_i \le 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

3
18 21 46

Sample Output 1

23

One way to make the smallest element 23 is as follows.

  • Initially, we have A=(18,21,46).
  • Divide A_1 by 2 and multiple A_1 by 3, making A=(27,21,46).
  • Divide A_3 by 2 and multiple A_2 by 3, making A=(27,63,23).

Sample Input 2

5
3 5 7 11 13

Sample Output 2

3

It may be impossible to do the operation at all.

Sample Input 3

1
536870912

Sample Output 3

68630377364883

The answer may not fit into a 32-bit integer type.