Chia nhóm


Submit solution

Points: 0.65 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
Ðược add lên bởi canhteo
Problem type

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~.


Comments


  • 0
    phanvanhuy  commented on 7, Jun, 2021, 16:43

    vi sao k chia moi so 1 nhom thi tong trong so se la 13 lon nhat


    • 0
      ngfam  commented on 7, Jun, 2021, 17:08

      Bạn đọc kỹ lại đề nhé!