Hệ tam phân (hay còn gọi là hệ cơ số 3) là hệ biểu diễn các số tự nhiên chỉ bằng các chữ số '~0~', '~1~', '~2~', dưới dạng tổng các lũy thừa của ~3~.

Số tam phân có ~m~ chữ số sẽ được biểu diễn dưới dạng "~c_{m-1}c_{m-2}...c_2c_1c_0~" với ~c_i \in \{0, 1, 2\}~. Số tam phân đó sẽ mang giá trị: $$c_{m-1} \times 3^{m-1} + c_{m-2} \times 3^{m-2} + ... + c_2 \times 3^2 + c_1 \times 3^1 + c_0 \times 3^0$$

Ví dụ: số tự nhiên ~5~ trong hệ thập phân sẽ được biểu diễn bằng số "~12~" (gồm ~2~ chữ số) trong hệ tam phân (vì ~5 = 1 \times 3^1+ 2 \times 3^0~); hoặc ngược lại, số có ~3~ chữ số là "~221~" trong hệ tam phân sẽ mang giá trị ~25~ trong hệ thập phân (vì ~25 = 2 \times 3^2 + 2 \times 3^1 + 1 \times 3^0~).

Cho mảng ~a~ gồm ~n~ phần tử là các số nguyên dương được biểu diễn dưới hệ thập phân.

Gọi ~f(x)~ là hàm trả về số lượng chữ số trong biểu diễn tam phân của ~x~, không tính những số ~0~ vô nghĩa ở đầu. Ví dụ: ~f(5) = 2~, ~f(25) = 3~.

Yêu cầu:

Tính giá trị nhỏ nhất có thể của ~f(a_i + a_j)~ (~\forall i,j: 1 \leq i, j \leq n~ và ~i \neq j~).

Input (vào từ TAMPHAN.INP)

• Dòng đầu chứa số nguyên dương ~n~ (~2 \leq n \leq 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ được biểu diễn dưới hệ thập phân, các số trên cùng một dòng cách nhau bởi dấu cách (~1 \leq a_i \leq 10^9~).

Output (xuất ra TAMPHAN.OUT)

• Gồm một số nguyên dương duy nhất là kết quả bài toán: giá trị nhỏ nhất có thể của ~f(a_i + a_j)~ (~\forall i,j: 1 \leq i, j \leq n~ và ~i \neq j~).

Ví dụ:

Sample Input 1

5
1 2 3 4 5

Sample Output 1

2

Note

• Khi chọn ~i = 1~, ~j = 3~, ta có ~a_1 + a_3 = 4~. Biểu diễn tam phân của ~4~ là "~11~", có ~2~ chữ số. Có thể chứng minh được không có lựa chọn tối ưu hơn (đáp án không thể bé hơn ~2~).

Subtask:

• ~20\%~ số test tương ứng với ~20\%~ số điểm có ~a_i + a_j < 9~ (~1 \leq i,j \leq n~ và ~i \neq j~).
• ~40\%~ số test tương ứng với ~40\%~ số điểm có ~n \leq 2000~.
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.