Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~, ~r~. Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy ~a_l, a_{l+1}, \dots, a_r~ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.

Input

Dòng đầu chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 5 \times 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).

~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~, ~r_i~ (~1 \le l_i \le r_i \le n~) mô tả truy vấn thứ ~i~.

Output

In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên là kết quả cho truy vấn thứ ~i~.

Sample Input 1

8 4
1 3 2 2 4 5 4 6
1 8
1 4
2 7
4 6

Sample Output 1

0
1
0
2