TWICE

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
vinhntndu
Dạng bài
Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

SPyofgame đang thực hiện một thử thách: đạt được mức Expert codeforces trong 1 tháng hoặc mất 50k. Trong lúc luyện tập, anh ấy gặp 1 bài toán như sau:

Cho mảng \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots A_N\), và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L,R\), và câu trả lời cho truy vấn là có bao nhiêu giá trị khác nhau xuất hiện đúng 2 lần trong đoạn \([L,R]\) của mảng \(A\).

Input

  • Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N, Q \leq 5*10^5)\).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots A_N\) \((A_i \leq 10^9)\)
  • \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L,R\) \((1 \leq L \leq R \leq N)\)

Output

  • In ra \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho truy vấn thứ \(i\).

Example

Test 1

Input 
5 1
1 2 1 1 1
1 3
Output 
1

Bình luận