Cho một dãy số gồm N phần tử, mỗi phần tử bằng -1 hoặc 1.

Có M truy vấn, mỗi truy vấn gồm hai số L và R, bạn cần tìm độ dài của dãy con liên tiếp dài nhất trong phạm vi từ L đến R (gồm cả L và R) mà có tổng bằng 0.

Input

Dòng đầu tiên chứa hai số nguyên N và M (1 <= N, M <= 50000) - số lượng phần tử của dãy số và số lượng truy vấn.

Dòng thứ hai chứa N số - các phần tử của dãy số, mỗi phần tử bẳng -1 hoặc 1.

Trong M dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 <= L <= R <= N).

Output

Với mỗi truy vấn, in ra độ dài của dãy số dài nhất thoả mãn yêu cầu. Nếu không có dãy nào phù hợp, in ra 0.

Ví dụ

  Input:
  6 4
  1 1 1 -1 -1 -1
  1 3
  1 4
  1 5
  1 6

  Output:
  0
  2
  4
  6