huyhau6a2 là một trong những thành viên của ban ra đề cho kỳ thi Codeforces Round 3636 (Div. 1 + 2), và cậu được chọn là người ra bài toán dễ nhất cho kỳ thi. Sau khi chuẩn bị xong, việc còn lại của huyhau6a2 là bảo mật đề thật tốt trước khi kỳ thi diễn ra. Tuy nhiên, thông tin về việc huyhau6a2 sẽ ra đề bằng cách nào đó đã bị tuồn ra, đã có rất nhiều người nhận thấy họ có thể ăn cắp đề để bán lấy tiền hoặc giữ lại để chuộc lợi cho bản thân. Vì thế nên họ đã tìm đủ mọi cách để xác định vị trí và đột nhập vào nơi giấu đề của huyhau6a2.

Biết trước được điều này, huyhau6a2 đã tạo ra một hệ thống bảo mật để bảo vệ đề thi trong ~q~ ngày sắp tới trước khi Codeforces Round đó bắt đầu. Bất kỳ ai không phải là người trong ban ra đề mà muốn truy cập vào đề thi của huyhau6a2 đều phải nhập mật khẩu. Đó là một mã số gồm ~n~ ký tự, mỗi ký tự có thể là một chữ số từ ~0~ đến ~9~. Hệ thống bảo mật đặc biệt cho phép mỗi ngày reset lại mật khẩu đúng, điều này giúp chỉ những người có quyền mới có thể truy cập một cách nhanh chóng. Đồng thời, hệ thống còn có một tính năng cho phép người nhập mật khẩu chỉ cần nhập một đoạn các ký tự từ ~l~ đến ~r~ của mật khẩu thay vì nhập hết, điều này làm giảm thời gian để nhập mật khẩu nhưng không ảnh hưởng nhiều đến tính bảo mật của đề thi. Giá trị ~l,r~ này được cố định trong suốt một ngày và sẽ reset lại vào ngày tiếp theo, khi nhập thì người nhập được biết trước hai giá trị này để có thể xác định chính xác đoạn mật khẩu cần phải nhập.

Với những người có quyền truy cập thì họ chỉ cần quét thẻ đặc biệt trong ~3.6~ giây thì đã có thể truy cập vào đề thi của huyhau6a2. Tuy nhiên với những người khác thì họ sẽ cần thời gian để đoán và nhập mật khẩu. Giả sử bạn - một người mới vô hệ thống để nhập mật khẩu, bạn có thể thực hiện một trong hai hành động sau đến khi hệ thống mở khóa:

• Nhập mật khẩu: Bạn nhập mật mã tương ứng với đoạn ký tự ~[l,r]~ của mật khẩu và hệ thống sẽ trả về mật mã mà bạn vừa nhập đúng hay sai, ngoài ra thì hệ thống không trả về gì thêm. Hành động này mất ~1~ đơn vị thời gian.
• Gợi ý mật khẩu: Bạn được phép chọn một ký tự ~i\ (l\le i\le r)~ và bạn sẽ biết được luôn giá trị của ký tự thứ ~i~ của mật khẩu. Tuy nhiên hành động này sẽ mất ~t_i~ đơn vị thời gian do hệ thống phải truy cập vào đám mây và còn nhiều yếu tố khác nữa để có thể trả về chính xác ký tự đó. Các giá trị ~t_i~ này là cố định và sẽ không bao giờ thay đổi theo ngày hay bất kỳ yếu tố nào khác.

Tuy hệ thống đã rất hoàn thiện nhưng huyhau6a2 muốn biết hệ thống của mình có thể bảo mật tốt trong ~q~ ngày sắp tới không. huyhau6a2 tin rằng nếu thời gian để một người mò mật khẩu càng lâu thì hệ thống bảo mật của mình càng mạnh. Vì thế nên huyhau6a2 đã viết một chương trình giúp xác định nhanh thời gian tối thiểu để một người mò mật khẩu từ đầu có thể truy cập vào đề thi của mình. Cảm thấy vấn đề này rất thú vị nên huyhau6a2 cũng muốn đem bài toán này ra để mọi người cùng thử sức, liệu các bạn có thể giải quyết bài toán hóc búa này không?

Trong bài toán này chúng ta chỉ giả định trường hợp từ khi một người bắt đầu mò mật khẩu đến khi truy cập vào được đề thi thì hệ thống không reset lại sang ngày mới, tức là giá trị ~l,r~ và các dữ liệu nhập mật khẩu trong suốt quá trình nhập sẽ ổn định và không thay đổi đến khi người đó nhập mật khẩu thành công.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ tương ứng với độ dài của mật khẩu và số ngày trước khi Codeforces Round diễn ra ~(1\le n,q\le 2\times 10^5)~.

Dòng thứ hai gồm ~n~ số nguyên ~t_1,t_2,\dots,t_n~ tương ứng với thời gian để hệ thống gợi ý ký tự thứ ~1,2,\dots,n\ (0\le t_i\le 10^9)~.

Dòng thứ ~j~ trong ~q~ dòng cuối cùng gồm hai số nguyên dương ~l_j,r_j~ tương ứng với đoạn ký tự ~[l_j;r_j]~ cố định của mật khẩu cần phải nhập trong ngày thứ ~j~ ~(1\le j\le q,1\le l_j\le r_j\le n)~.

Output

In ra ~q~ dòng, dòng thứ ~j~ gồm duy nhất một số nguyên là thời gian tối thiểu để một người có thể truy cập vào đề thi nếu muốn truy cập vào ngày thứ ~j~.

Sample Input

6 2
0 1 6 7 1 1
6 6
1 2

Sample Output

1
1