Du lịch

Vương quốc ZXY có $n$ thành phố du lịch nổi tiếng, được đánh số thứ tự từ $1$ tới $n$. Sơn là một du khách muốn thực hiện một hành trình du lịch qua $n$ thành phố này. Thành phố $i$ có điểm đánh giá của cộng đồng là $a_i$. Đối với mỗi thành phố, Sơn có thể lựa chọn hình thức ghé thăm là lượt qua (trong ngày, không ngủ lại) hay bình thường (có ngủ lại một đêm). Để đánh giá chất lượng của mỗi lượt thăm một thành phố, Sơn đề ra quy tắc tính sau:

• Nếu lượt qua thành phố $i$, điểm chất lượng sẽ là $(a_i-c{)}^2$ với $c$ là hằng số cho trước.
• Nếu thăm bình thường thành phố $i$, điểm chất lượng sẽ là $(a_i-a_p{)}^2$ với $p$ là thành phố thăm bình thường gần nhất trước đó. Nếu $i$ là thành phố thăm bình thường đầu tiên, điểm chất lượng của thành phố này bằng $0$.

Sơn muốn hành trình của mình thăm các thành phố theo đúng thứ tự $1,2,\dots ,n$, mỗi thành phố đúng một lần, các thành phố $1$ và thành phố $n$ phải được thăm bình thường, điểm chất lượng của thành phố $1$ bằng $0$.

Yêu cầu: Hãy xác định tổng điểm chất lượng lớn nhất mà Sơn có thể đạt được sau hành trình của mình.

Dữ liệu vào

• Dòng 1: hai số nguyên $n,c$ ($1\le n\le {10}^6$; $-{10}^6\le c\le {10}^6$).
• Dòng 2: $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($-{10}^6\le a_i\le {10}^6$).

Dữ liệu ra

Tổng điểm chất lượng lớn nhất mà Sơn có thể đạt được.

Ràng buộc

• $1\le n\le {10}^6$.
• $-{10}^6\le c\le {10}^6$, $-{10}^6\le a_i\le {10}^6$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 500$.
• Subtask 2 ($20\%$ số điểm): $n\le 5000$.
• Subtask 3 ($20\%$ số điểm): $a_i\le a_{i+1}$, với $1\le i<n$.
• Subtask 4 ($30\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ