Cho 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~ (~i = 1, 2, \dots, n~), 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 bi.

Mỗi lượt, chỉ một người (có số lượng bi lớn hơn 0) được phép chuyển một viên bi 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 của Ban tổ chức nếu sau khi thực hiện dãy các lượt chuyển bi thì có không quá một người có số bi là một số lẻ. Nếu biết thời gian để chuyển một viên bi 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~ và ~n~ số nguyên không âm ~a_1, a_2, \dots, 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.

Dữ liệu

Vào từ file văn bản CHUYENBI.INP

• Dòng đầu tiên chứa ba số nguyên dương ~n, L, R~ (~1 \le L, R \le 10^6~);
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~) là số bi mà người thứ ~i~ được phát.

Kết quả

Đưa ra file văn bản CHUYENBI.OUT gồm một dòng là kết quả bạn tính được.

Ví dụ

CHUYENBI.INP

5 3 2
1 2 3 4 5

CHUYENBI.OUT

2

Giới hạn

• Subtask 1 (25% số test, 25% số điểm): ~n = 3~;
• Subtask 2 (25% số test, 25% số điểm): ~n \le 1000~ và chỉ có đúng hai người có số bi là số lẻ;
• Subtask 3 (25% số test, 25% số điểm): ~n \le 1000~;
• Subtask 4 (25% số test, 20% số điểm): ~n \le 10^5~.