Đế chế

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
invisible , kieulqd
Dạng bài
Điểm: 1700 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trong tiết học lịch sử của trường mầm non super kids, các em nhỏ đã được học về lịch sử của một đất nước xa xôi. Lịch sử của đất nước này được chia làm \(N\) mốc thời gian. Tại một mốc thời gian bất kỳ, một đế chế mới sẽ xuất hiện, mỗi đế chế sẽ có một sức mạnh nhất định, không có hai đế chế nào có cùng chỉ số sức mạnh. Đế chế thứ \(i\) sẽ có chỉ số sức mạnh là \(a_i\). Với mỗi mốc thời gian bất kỳ, các đế chế có chỉ số sức mạnh cao hơn sẽ đi xâm chiếm những đế chế yếu có chỉ số sức mạnh thấp hơn. Cuộc chiến sẽ diễn ra đến khi chỉ còn một đế chế duy nhất tồn tại, và ta gọi đế chế này là đế chế thống trị trong mốc thời gian đang xét.

Để ra đề kiểm tra khả năng hiểu bài của các bạn học sinh, thầy giáo đã cho các em ấy \(Q\) câu hỏi. Với mỗi câu hỏi bất kỳ, thầy giáo sẽ cho các bạn học sinh hai số nguyên dương \(L\) và \(R\) đại diện cho giai đoạn từ mốc thời gian \(L\) đến mốc thời gian \(R\). Yêu cầu của mỗi câu hỏi là: nếu chỉ tính trong các đế chế trong giai đoạn này, hãy tính độ đa dạng của giai đoạn lịch sử \([L, R]\).

Độ đa dạng của giai đoạn lịch sử \([L, R]\) là số lượng đế chế có ít nhất một lần thống trị một mốc thời gian nào đó thuộc \([L, R]\).

Input

  • Dòng đầu tiên là hai số nguyên dương \(N, Q\) lần lượt là số lượng mốc thời gian trong lịch sử và số lượng câu hỏi \((1 \leq N,Q \leq 5 \times 10^5)\).
  • Dòng tiếp theo là một dãy a bao gồm \(N\) số, \(a_i\) là chỉ số sức mạnh của đế chế xuất hiện ở mốc thời gian \(i\) \((1 \leq i \leq N, 1 \leq a_i \leq 2 \times 10^9)\).
  • \(Q\) dòng tiếp theo mỗi dòng hai số nguyên dương \(L, R\) \((1 \leq L \leq R \leq N)\).

Output

  • Gồm \(Q\) dòng là câu trả lời cho các câu hỏi.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N,Q \leq 5 \times 10^3\).
  • Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
5 2    
1 2 4 3 5
1 3
2 4
Output 
3
2
Note

Giải thích giai đoạn [2, 4].

Mốc thời gian thứ hai: đế chế 2 xuất hiện và là đế chế duy nhất -> thống trị mốc thời gian thứ hai.

Mốc thời gian thứ ba: đế chế 3 xuất hiện với chỉ số sức mạnh là 4 -> thống trị mốc thời gian thứ ba.

Mốc thời gian thứ tư: đế chế 4 xuất hiện với chỉ số sức mạnh là 3, bị đế chế 3 xâm chiếm.

Bình luận