Hạo bị chấn thương nhẹ ở chân và phải đi phẫu thuật đầu gối.

Còn \(q\) ngày nữa mới tới lịch phẫu thuật, mà Hạo mỗi ngày phải đi qua một trong số \(n\) ngọn núi xếp liên tiếp. Cụ thể, ở ngày thứ \(i\), Hạo cần di chuyển từ ngọn núi \(l_i\) đến ngọn núi \(r_i\).

Hiện tại, Hạo không thể xuống dốc (dù vẫn có thể lên dốc). Thật may, vì là thần núi, Hạo có thể niệm chú cho một ngọn núi cao lên \(1\) đơn vị vô số lần, để ngọn núi trước mặt không thấp hơn ngọn núi Hạo đang đứng. Tuy nhiên, niệm chú sẽ tốn năng lượng, nên Hạo muốn làm điều này càng ít càng tốt.

Cho biết độ cao của các ngọn núi và lịch trình \(q\) ngày tiếp theo của Hạo, hãy giúp Hạo ấy tính số lần niệm chú tối thiểu cho mỗi ngày.

Dữ liệu vào:

• Dòng đầu tiên gồm \(2\) số nguyên \(n, q\) \((1 \le n, q \le 2 \times 10^5)\) - số ngọn núi và số ngày trong lịch trình.
• Dòng tiếp theo gồm n số nguyên \(A_i\) \((1 \le A_i \le 10^9)\) - độ cao của các ngọn núi.
• \(q\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(l_i, r_i\) \((1 \le l_i \le r_i \le n)\), cho biết Hạo đi từ ngọn núi \(l\) đến ngọn núi \(r\).

Dữ liệu ra:

In ra \(q\) dòng, mỗi dòng gồm một số nguyên duy nhất cho biết số lần tối thiểu Hạo phải niệm chú.

Input 1

5 3
2 1 4 2 5
1 4
4 5
2 4

Output 1

3
0
2