Coder bị nghiện game nặng. Trò chơi của anh ấy có dãy n phần thưởng liên tiếp riêng biệt và có 2 sự kiện. Tham gia sự kiện A sẽ lấy được phần thưởng ở đầu dãy, tham gia sự kiện B sẽ lấy được phần thưởng ở cuối dãy. Khi phần thưởng bị lấy đi thì nó sẽ biến mất. Coder muốn lấy được phần thưởng có giá trị cao nhất và thấp nhất, mỗi lần lấy một phần thưởng, anh ấy sẽ tốn số coin tương ứng với giá trị phần thưởng ấy. Ví dụ : n = 5 và a = [1, 5, 4, 3, 2], Coder có thể thực hiện các hành động sau:

• Tham gia sự kiện A và tốn 1 coin.
• Tham gia sự kiện A và tốn 5 coin.
• Sau hành động này, Coder đã có được phần thưởng lớn nhất và phần thưởng nhỏ nhất, vậy nên anh ấy dừng lại, số coin đã dùng là 6.

Hãy giúp Coder tính toán được số coin ít nhất để anh ấy lấy được 2 phần thưởng mong muốn.

Input

• Dòng đầu tiên gồm 1 số nguyên dương n là số phần thưởng (1 ≤ n ≤ 10⁶).
• Dòng tiếp theo gồm n số nguyên riêng biệt a₁, a₂, ..., a_n (1 ≤ a_i ≤ n).

Output

Là đáp án của bài toán.

Examples