Trò chơi trí tuệ

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 kẹo 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ẻ. 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ời gian của cả dãy lượt chuyển là tổng thời gian của các lượt. Nếu ngay từ đầu đã có không quá một người có số kẹo lẻ thì nhóm thắng mà không cần chuyển kẹo (thời gian bằng $0$).

Yêu cầu: Cho số nguyên dương $n$, $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ và hai số nguyên dương $L,R$. Hãy tính thời gian ít nhất để nhóm giành chiến thắng.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $n,L,R$ ($n\le {10}^5$, $L,R\le {10}^6$).
• Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ ($a_i\le {10}^6$) là số kẹo mà người thứ $i$ được phát.

Dữ liệu ra

In ra một số nguyên là thời gian ít nhất để nhóm giành chiến thắng.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le L,R\le {10}^6$.
• $0\le a_i\le {10}^6$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $n\le 3$.
• Subtask 2 ($25\%$ số điểm): $n\le 1000$, chỉ có đúng hai người có số kẹo là lẻ.
• Subtask 3 ($25\%$ số điểm): $n\le 1000$.
• Subtask 4 ($25\%$ số điểm): $n\le {10}^5$.

Ví dụ