#2333. BEAUTARR - Dãy đẹp

Tải đề bài (PDF)

Một dãy số được gọi là "đẹp" nếu mỗi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá 2. Ví dụ:

• [1, 5, 2, 4, 3], [6, 10, 10, 6] và [9] là các dãy đẹp.
• [3, 3, 3, 4, 4], [7, 7, 8, 7] và [100, 100, 100] không phải là các dãy đẹp.

Cho dãy A độ dài , hãy đếm số cặp chỉ số (l, r) với sao cho dãy con là dãy đẹp.

Dữ liệu:

• Dòng đầu tiên: gồm số nguyên N () - độ dài dãy A;
• Dòng thứ hai: gồm N số nguyên () là các phần tử của dãy A.

Kết quả:

• Một số nguyên duy nhất là số cặp chỉ số (l, r) thỏa mãn yêu cầu đề bài.

Ví dụ:

Dữ liệu:

4
1 2 1 1

Kết quả:

9

Giải thích:

• Ở ví dụ thứ nhất, có 9 cặp chỉ số (l, r) thỏa mãn yêu cầu đề bài:
  • l = 1, r = 1 (dãy [1])
  • l = 1, r = 2 (dãy [1, 2])
  • l = 1, r = 3 (dãy [1, 2, 1])
  • l = 2, r = 2 (dãy [2])
  • l = 2, r = 3 (dãy [2, 1])
  • l = 2, r = 4 (dãy [2, 1, 1])
  • l = 3, r = 3 (dãy [1])
  • l = 3, r = 4 (dãy [1, 1])
  • l = 4, r = 4 (dãy [1])

Giưới hạn:

• Subtask 1: ( số điểm): , ;
• Subtask 2: ( số điểm): , ;
• Subtask 3: ( số điểm): , ;
• Subtask 4: ( số điểm): Không có ràng buộc gì thêm.