Cho dãy số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\). Hãy thực hiện \(Q\) yêu cầu, mỗi yêu cầu được cho bởi hai số nguyên \(L, R\) \((1 \leq L \leq R \leq n)\) với ý nghĩa tính:

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, Q\) \((1 \leq n, Q \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) mô tả yêu cầu thứ \(i\) gồm hai số nguyên \(L_{i}, R_{i}\) \((1 \leq L_{i} \leq R_{i} \leq n)\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) ghi một số nguyên là câu trả lời của yêu cầu thứ \(i\) (in \(0\) nếu tất cả các giá trị trong yêu cầu tương ứng khác nhau).

Examples

7 5
4 5 6 6 5 7 4
6 6
5 6
3 5
3 7
1 7

0
0
1
1
6