Cho dãy gồm N ~(1 \le N \le 10^5)~ số nguyên ~A_1, A_2, A_N; (0 < A_i \le 10^5)~. Với bộ ba số (i,j,k) trong đó ~1 \le i < j < k \le N~ hãy tìm giá trị ~S= 2A_i + A_j + 3A_k~ sao cho S đạt giá trị nhỏ nhất.

Input:

Được cho bởi tệp lowmax.inp có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên ~A_1, A_2,..., A_N~ giữa các số cách nhau một khoảng trắng.

Output:

Được cho bởi tệp lowmax.out có cấu trúc như sau:

• In ra một số duy nhất là số S nhỏ nhất tìm được.

Example

Input

9
5 4 4 4 1 4 6 8 7

Output

15