Trong buổi giao lưu giữa các đoàn tham gia Trại hè Phương Nam, Ban tổ chức mời các thí sinh tham gia một trò chơi như sau:

Chọn một nhóm gồm ~n~ người ngồi vào ~n~ vị trí, các vị trí được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ quanh bàn tròn. Người ngồi ở vị trí ~i~ gọi là người thứ ~i~, như vậy, với người thứ nhất, bên phải là người thứ ~n~, bên trái là người thứ ~2~; với người thứ ~2~ bên phải là người thứ nhất, bên trái là người thứ ~3~; ...; còn với người thứ ~n~, bên phải là người thứ ~(n - 1)~, bên trái là người thứ nhất. Người thứ ~i~ được phát ~a_i (a_i \ge 0)~ viên kẹo. Mỗi lượt, chỉ một người (có số lượng kẹo lớn hơn ~0~) được phép chuyển một viên của mình cho người bên trái hoặc người bên phải. Nhóm sẽ giành chiến thắng và nhận được phần thưởng nếu sau khi thực hiện dãy các lượt chuyển kẹo thì có không quá một người có số kẹo là một số lẻ. Nếu biết thời gian để chuyển một viên kẹo sang cho người bên trái là ~L~ và sang cho người bên phải là ~R~ thì có thể tính toán chính xác thời gian ít nhất để nhóm giành chiến thắng.

Yêu cầu: Cho số nguyên dương ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ và hai số nguyên dương ~L, R~. Bạn hãy lập trình tính thời gian ít nhất để nhóm giành chiến thắng.

Input

Dòng đầu tiên chứa ba số nguyên dương ~n, L, R~ (~L, R \le 10^6~).

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ (~a_i \le 10^6~) là số kẹo mà người thứ ~i~ được phát.

Output

Thời gian ít nhất để nhóm giành chiến thắng.

Scoring

Sample Input 1

5 3 2
1 2 3 4 5

Sample Output 1

2