Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMLSEQ - Dãy số may mắn

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmlseq


Công ty XYZ có m nhân viên. Gần tết công ty quyết định tố chức trò chơi cho các nhân viên của mình. Trò chơi chuẩn bị trước 1 dãy số N số và M yêu cầu. Mỗi nhân viên tham gia trò đều được cho một yêu cầu là chọn tùy ý 1 dãy liên tiếp các số trong đoạn từ L tới R rồi sau đó đưa cho ban tổ chức để nhận thưởng. Với tiêu chí vui là chính nên ai cũng sẽ có mức thưởng ban đầu như nhau. Tuy nhiên những ai chọn được một dãy số may mắn thì sẽ được thưởng nhiều hơn. Phần thưởng cho nhân viên nào chọn trúng được dãy số may mắn có giá trị là X đơn vị tiền tệ trong đó X là độ dài dãy số may mắn mà nhân viên đó chọn được. Để chuẩn bị phần thưởng ban tổ chức muốn biết với mỗi yêu cầu thì phần thưởng có giá trị lớn nhất là bao nhiêu.


Dãy số được gọi là may mắn nếu thỏa mãn tất cả các điều kiện sau:

  • Dãy số {x, -x} được gọi là dãy số may mắn.

  • Dãy số {x, S, -x} được gọi là dãy số may mắn nếu S là dãy số may mắn.

  • Dãy số {S1, S2} được gọi là dãy số may mắn nếu S1 và S2 là 2 dãy số may mắn.

Vì quá bận cho khâu trang trí công ty cho dịp Tết sắp tới nên ban tổ chức đã nhờ đến các coder VNOI giúp đỡ.

Input

  • Dòng đầu tiên chứa 2 số nguyên dương N, M.
  • Dòng thứ 2 chứa N số miêu tả dãy số được chuẩn bị trước của trò chơi.
  • Dòng thứ i trong M dòng tiếp theo chứa 2 số Li, Ri miêu tả yêu cầu của nhân viên thứ i. 

Output

  • Dòng thứ i trong M dòng là kết quả cho yêu cầu của nhân viên thứ i.

Giới hạn

  • 1 ≤ N, M ≤ 200000
  • Các số được chuẩn bị trước là các số nguyên khác 0 và có giá trị tuyệt đối không vượt quá 105
  • 1 ≤ Li ≤ Ri ≤ N
  • 30% số test có N, M ≤ 1000

Example

Input:

10 2

2 1 -1 -2 5 1 -1 7 -7 5

1 7

7 10

Output:

4

2


Được gửi lên bởi:VOJ Team
Ngày:2014-08-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Marathon 2014 - Trần Phan Anh Khoa

hide comments
2018-03-12 15:07:20


Last edit: 2018-03-12 15:20:43
2014-08-14 21:48:14 VOJ Team
Bộ test vừa được sửa, các bài nộp đã được rejudge. Xin lỗi các bạn về sai sót này.
2014-08-04 23:55:07 Stupid Dog
Nếu mình không hiểu sai đề thì nhân viên nào cũng chọn từ 1 -> n là sướng nhất
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.