Cho một dãy gồm N số nguyên A được đánh số từ 0 và Q truy vấn. Mỗi truy vấn có dạng (l, r) yêu cầu tìm dãy con liên tiếp dài nhất trong đoạn con từ ~ A_l, ..., A_r ~ sao cho không có hai phần tử nào trong dãy con tìm được bằng nhau.

Input

• Dòng đầu tiên: chứa hai số nguyên N, Q (~ N, Q ≤ 10^5 ~).

• Dòng thứ hai: gồm N số nguyên dương (~ |A_i| ≤ 10^{18} ~).

• Q dòng tiêp theo: mỗi dòng gồm 2 số l, r (0 ≤ l ≤ r < N) tương ứng với một câu hỏi.

Output

• Gồm Q dòng tương ứng với câu trả lời của Q truy vấn

Sample

Input #1

9 2
0 3 2 -1 0 1 4 0 2
0 8
2 6

Output #1

6
5

Problem source: Free Contest 57