Trên con đường dẫn vào thành phố du lịch nổi tiếng, có một hàng cây được trồng ven đường gồm \(n\) cây được đánh số từ \(1\) đến \(n\) theo chiều từ đầu đến cuối con đường, trong đó cây thứ \(i\) có chiều cao \(h_i\). Để thu hút khách du lịch, chính quyền thành phố muốn cải tạo hàng cây sao cho hấp dẫn nhất. Chính quyền đưa ra các phương án và cần đánh giá các phương án để lựa chọn. Cụ thể, với mỗi phương án được mô tả bằng hai số \(L,R\), khi đó các cây có chiều cao nằm ngoài khoảng \([L,R]\) sẽ bị loại bỏ và để đánh giá phương án có khả thi hay không cần tính tổng chênh lệch chiều cao giữa hai cây liên tiếp được giữ lại.

Yêu cầu: Cho biết chiều cao của \(n\) cây và \(q\) phương án, hãy lập trình đưa ra tổng chênh lệch chiều cao giữa hai cây liên tiếp còn được giữ lại trong mỗi phương án.

Input

• Dòng đầu chứa số nguyên \(n,q\) (\(1 \le n,q \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(h_i\) (\(1 \le h_i \le 10^9\)).
• Tiếp theo là \(q\) dòng, dòng thứ \(j\) chứa hai số nguyên \(L_j,R_j\) (\(1 \le L_j \le R_j \le 10^9\)) mô tả một phương án.

Output

• Với mỗi phương án đưa ra kết quả trên một dòng là tổng chênh lệch chiều cao giữa hai cây liên tiếp được giữ lại.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n,q \le 5000\).
• Subtask \(2\) (\(20\%\) số điểm): \(h_i \le 400\).
• Subtask \(3\) (\(20\%\) số điểm): \(L_j \le L_{j+1}, R_j \le R_{j+1}\).
• Subtask \(4\) (\(20\%\) số điểm): \(n,q \le 7 \times 10^4\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

7
5
3
3
1