Thiết Mộc Chân có một đội quân vô cùng hùng mạnh, ông quyết dùng đội quân này để đi xâm lược mở rộng lãnh thổ. Đội quân của ông có \(n\) chiến binh được đánh số từ \(1\) đến \(n\) có sức mạnh lần lượt là \(a_{1}, a_{2}, \ldots, a_{n}\).

Mỗi chiến binh trong đội quân của ông đều có niềm kiêu hãnh vô cùng lớn nên nếu được phân nhóm,chiến binh đó không muốn có ai khác trong nhóm có cùng sức mạnh với mình.

Giả sử Thiết Mộc Chân chọn một nhóm \(k\) người có sức mạnh là \((x_{1}, x_{2}, \ldots, x_{k})\) thì nhóm này sẽ được chia ra như sau:

• Nếu nhóm này không có \(2\) chiến binh nào có sức mạnh bằng nhau thì dừng lại.
• Nếu nhóm này có ít nhất \(2\) chiến có sức mạnh bằng nhau thì ta chia nhóm này thành \(2\) nhóm các chiến binh chỉ số lẻ \((x_{1}, x_{3}, \ldots)\), và nhóm các chiến binh có chỉ số chẵn \((x_{2}, x_{4}, \ldots)\) và sau đó ta lại tiếp tục quy trình chia như đã nói với \(2\) nhóm này.

Và với một nhóm như vậy Thiết Mộc Chân cần biết nhóm đó được tách thành bao nhiêu nhóm qua quy trình trên để ông bàn chiến thuật tác chiến.

Thiết Mộc Chân muốn thử nghiệm \(q\) giả định chiến đấu, cụ thể như sau:

Với gỉa định chiến đấu thứ \(i\) ông sẽ chọn ra một nhóm gồm các binh sĩ có chỉ số sức mạnh \((a_{l_i}, a_{l_i+1}, \ldots,a_{r_i})\) để đi chiến đấu. Với mỗi ngày, bạn hãy giúp Thiết Mộc Chân tính xem số nhóm được chia ra từ nhóm ông đã chọn nhé.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\) lần lượt là số binh lính và số ngày đánh trận.
• Dòng thứ \(2\) gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq n)\) là sức mạnh của các binh lính.
• \(q\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả nhóm Thiết Mộc Chân chọn đi chiến đấu vào ngày thứ \(i\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là một số nguyên là số nhóm chia ra được vào ngày thứ \(i\).

Scoring

• Subtask \(1\) (\(7\%\) số điểm): \(a_{i} = 1\) với mọi \(i\) từ \(1\) đến \(n\);
• Subtask \(2\) (\(13\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(3\) (\(15\%\) số điểm): \(n \leq 10^{3}\) và \(l_{i} = 1, \forall i:1 \leq i \leq q\)
• Subtask \(4\) (\(17\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(5\) (\(23\%\) số điểm): \(n, q \leq 10^{4}\).
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

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

1
2
3

5 2
1 4 2 4 1
1 5
2 4

5
3