Đề bài

Zoran là người trông coi vườn thú Zagreb. Hiện anh đang nghiên cứu khoa học về mối quan hệ giữa mức độ hài lòng của khách tham quan và cách các loài động vật được bố trí trong vườn thú.

Hành trình của một khách tham quan qua toàn bộ vườn thú có thể được xem là một dãy gồm \(N\) khu nuôi, mỗi khu chứa một loài động vật nhất định. Ban đầu, khu nuôi thứ \(i\) chứa động vật thuộc loài \(a_i\), và khách tham quan sẽ quan sát các khu nuôi theo thứ tự.

Zoran bắt đầu thử nghiệm những cách thay đổi thứ tự bố trí động vật. Sau đó, anh đặt ra các câu hỏi về mức độ hài lòng của khách trong chuyến tham quan. Hóa ra khách hài lòng nhất khi tổng độ đa dạng của hành trình nhỏ nhất có thể.

Độ đa dạng của một dãy khu nuôi là số loài động vật khác nhau có thể quan sát trong các khu nuôi đó. Tổng độ đa dạng của một dãy khu nuôi là tổng độ đa dạng của tất cả các dãy con liên tiếp của nó.

Ví dụ, độ đa dạng của dãy \((1,1,2)\) là \(2\) vì dãy này có hai loài khác nhau. Tổng độ đa dạng của dãy là \(8\), vì các dãy con liên tiếp \((1)\), \((1)\), \((2)\), \((1,1)\), \((1,2)\) và \((1,1,2)\) lần lượt có độ đa dạng \(1,1,1,1,2,2\).

Zoran biết loài động vật hiện đang ở mỗi khu nuôi. Trước khi sắp xếp lại vườn thú, anh muốn bạn trả lời \(Q\) truy vấn độc lập. Trong truy vấn thứ \(i\), anh muốn biết tổng độ đa dạng nhỏ nhất có thể của dãy con liên tiếp từ khu nuôi \(l_i\) đến khu nuôi \(r_i\), nếu được phép sắp xếp lại các động vật đang sống trong những khu nuôi này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), trong đó \(a_i\) là loài động vật đang ở khu nuôi thứ \(i\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\) (\(1\le l_i\le r_i\le N\)), mô tả một truy vấn.

Các truy vấn hoàn toàn độc lập với nhau. Nói cách khác, khi trả lời mỗi truy vấn, hãy giả sử khu nuôi thứ \(i\) ban đầu vẫn chứa loài \(a_i\).

Dữ liệu ra

Dòng thứ \(i\) chứa một số nguyên duy nhất là đáp án của truy vấn thứ \(i\).

Chấm điểm

• Subtask 1 (4 điểm): \(1\le N\le11\), \(1\le a_i\le300\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 2 (10 điểm): \(1\le N\le300\,000\), \(1\le a_i\le11\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 3 (8 điểm): \(1\le N\le300\,000\), \(1\le a_i\le23\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 4 (16 điểm): \(1\le N\le300\,000\), \(1\le a_i\le1\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 5 (26 điểm): \(1\le N\le300\,000\), \(1\le a_i\le300\,000\), \(Q=1\), \(l_1=1\), \(r_1=N\).
• Subtask 6 (36 điểm): \(1\le N\le300\,000\), \(1\le a_i\le300\,000\), \(1\le Q\le50\,000\).

Ví dụ

3 1
1 2 3
1 3

10

4 2
1 1 1 1
1 2
2 4

3
6

5 3
1 2 1 3 2
2 5
1 3
3 4

16
8
4