Cho ~N~ số nguyên dương ~A_1, A_2, ..., A_N~. Mỗi số có giá trị không vượt quá ~N~.

Yêu cầu:

Hãy chia ~N~ số này thành một số nhóm sao cho:

• Mỗi nhóm là một dãy các số liên tiếp.
• Trọng số của mỗi nhóm được tính theo công thức: Bình phương của số giá trị khác nhau trong nhóm đó.

Ví dụ:

• ~1\ 2\ 3~ ~\rightarrow~ số giá trị khác nhau bằng ~3~, trọng số ~= 9~.
• ~1\ 2\ 1~ ~\rightarrow~ số giá trị khác nhau bằng ~2~, trọng số ~= 4~.
• ~1\ 1\ 1~ ~\rightarrow~ số giá trị khác nhau bằng ~1~, trọng số ~= 1~.

Trọng số của dãy số bằng Tổng trọng số của tất cả các nhóm. Hãy tìm cách chia sao cho Tổng trọng số đạt giá trị nhỏ nhất.

Input

Dòng ~1~: Gồm ~2~ số ~N~ và ~M~ - Số lượng số và số giá trị khác nhau trong dãy.

Dòng ~2~ ...~N+1~: Mỗi dòng chứa một số nguyên.

Output

Trọng số nhỏ nhất của dãy số.

Sample Input

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

Sample Output

11

Note

Giải thích: Chúng ta sẽ chia dãy số thành ~8~ nhóm

• ~4~ nhóm đầu tiên mỗi nhóm chứa một số duy nhất.
• nhóm thứ ~5~ chứa hai số nguyên đều có giá trị là ~2~.
• nhóm thứ ~6~ gồm các số từ ~7~ ~\rightarrow~ ~12~: ~(3~, ~4~, ~3~, ~4~, ~3)~
• ~2~ nhóm cuối cùng mỗi nhóm gồm ~1~ số duy nhất.

Kết quả là ~1^{2}~ + ~1^{2}~ + ~1^{2}~ + ~1^{2}~ + ~1^{2}~ + ~2^{2}~ + ~1^{2}~ + ~1^{2} =~ ~11~.

Giới hạn: ~N \le 40000~.