Vào một ngày đẹp trời, ~N~ thành viên đội tuyển tin CVP quyết định rủ nhau đi xem phim. Hôm nay là ngày khuyến mãi nên rạp phim bán vé theo một hình thức đặc biệt:

• Vé phát cho mọi người là các số nguyên phân biệt nằm trong khoảng ~[1, 10^9]~.
• Bình thường tiền thu vé của một đoàn người là giá vé * (mã vé max - mã vé min) nhưng hôm nay bất kỳ đoàn nào đi xem phim đều chỉ phải cử ra hai người có mã số vé ~L~ và ~R~ ~(L < R)~, rạp sẽ thu một khoản tiền bằng tổng chữ số của tất cả các số nguyên nằm trong khoảng ~[L, R]~.

Do quân số đông và khó kiểm soát nên các thành viên đội tuyển tin dẫn nhau đi xem phim lẻ, tức là một đoạn liên tiếp các thành viên trong hàng ~N~ người sẽ đi xem phim riêng và nhóm này sẽ phải trả tiền xem phim theo cách đã nói. Để giúp các nhóm này tiết kiệm chi phí, đội trưởng yêu cầu bất cứ nhóm nào cũng phải mua vé theo chiến thuật: cử hai người có mã số vé lớn nhất và lớn nhì đi trả tiền. Hãy giúp đội trưởng xác định số tiền tối đa mà một nhóm phải trả cho rạp là bao nhiêu ?

Input

• Dòng ~1:~ Số nguyên dương ~N~ ~(N > 1)~.
• Dòng ~2:~ ~N~ số nguyên dương, số thứ ~i~ là mã vé của thành viên thứ ~~.

Output

• Một dòng duy nhất ghi số tiền nhiều nhất mà một nhóm nào đó phải trả.

Giới hạn:

• ~50\%:~ ~N \le 10^3~.
• ~50\%:~ ~10^3 < N \le 10^5~.

Example

Input

3
9 10 11

Output

10