Bạn đang chơi một trò chơi giải đố với $n$ viên đá quý xếp thành một hàng, được đánh số từ $1$ đến $n$ từ trái sang phải. Viên đá quý thứ $i$ có màu $c[i]$.
Tại bất kỳ thời điểm nào, bạn có thể chọn hai viên đá quý kề nhau có cùng màu và loại bỏ chúng. Sau đó, các viên đá quý ở hai bên sẽ trượt lại gần nhau để lấp đầy khoảng trống, có thể tạo ra các cặp kề nhau mới.
Bạn sẽ được cung cấp $q$ kịch bản độc lập. Trong kịch bản thứ $j$, bạn chỉ xét các viên đá quý bắt đầu từ viên $l[j]$ đến viên $r[j]$. Giả sử bạn thực hiện một chuỗi các thao tác loại bỏ tối ưu, số lượng viên đá quý tối thiểu còn lại là bao nhiêu?
Dữ liệu vào
Chương trình của bạn phải đọc từ thiết bị nhập tiêu chuẩn.
Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ cách nhau bởi dấu cách.
Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $c[1], c[2], \dots, c[n]$ cách nhau bởi dấu cách.
$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Dòng thứ $i$ trong số này chứa $l[i]$ và $r[i]$.
Dữ liệu ra
Chương trình của bạn phải in ra thiết bị xuất tiêu chuẩn.
Dữ liệu ra nên chứa $q$ dòng. Dòng thứ $i$ trong số này nên chứa một số nguyên là câu trả lời cho kịch bản thứ $i$.
Giới hạn
Với tất cả các bộ dữ liệu, đầu vào sẽ thỏa mãn các giới hạn sau:
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ với mọi $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ với mọi $1 \le j \le q$
Chương trình của bạn sẽ được kiểm tra trên các bộ dữ liệu thỏa mãn các hạn chế sau:
| Nhiệm vụ con | Điểm | Giới hạn bổ sung |
|---|---|---|
| 0 | 0 | Các bộ dữ liệu mẫu |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | Các viên đá quý cùng màu tạo thành một mảng con liên tiếp (Nếu $c[i] = c[j]$ và $i < j$, thì $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$ với mọi $1 \le j \le q$ |
| 5 | 8 | Có đúng hai viên đá quý cho mỗi màu |
| 6 | 16 | $c[i] \le 2$ với mọi $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | Không có giới hạn bổ sung |
Ví dụ
Dữ liệu vào 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
Dữ liệu ra 1
1 0 1 4
Ghi chú
Bộ dữ liệu này hợp lệ cho các nhiệm vụ con 3, 7, 8, và 9. $n = 8$ viên đá quý được hiển thị trong sơ đồ dưới đây.
Trong kịch bản đầu tiên, chỉ ba viên đá quý đầu tiên được xét. Việc loại bỏ bất kỳ hai viên đá quý kề nhau nào sẽ để lại đúng một viên, sau đó không thể loại bỏ thêm viên nào nữa. Do đó, câu trả lời là 1.
Trong kịch bản thứ hai, các viên đá quý có thể được loại bỏ theo cách sau, không để lại viên nào:
Trong kịch bản thứ ba, các viên đá quý có thể được loại bỏ theo cách sau, để lại một viên:
Trong kịch bản thứ tư, không có viên đá quý nào có thể bị loại bỏ. Do đó, câu trả lời là 4.
Dữ liệu vào 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
Dữ liệu ra 2
2 0 0
Ghi chú
Bộ dữ liệu này hợp lệ cho các nhiệm vụ con 3, 6, 7, 8, và 9.