Có \(n\) tòa nhà tòa thứ \(i\) có độ cao \(h_i\). Bạn chỉ có thể di chuyển từ tòa nhà thứ \(x\) sang tòa nhà thứ \(x-1\) hoặc tòa nhà thứ \(x+1\) . May mắn được vị thần tặng một đôi giày thần kì, khi mang nó vào, bạn có thể bay từ tòa nhà này sang tòa nhà khác trong thời gian vô hạn với cách bay cụ thể như sau: Khi bạn bay từ tòa nhà thứ \(p\) sang tòa nhà thứ \(q\), nếu \(h_p>h_q\) thì bạn sẽ bị mất đi \(h_p-h_q\) năng lượng, ngược lại, bạn sẽ không mất bất kì năng lượng nào.

Có Q truy vấn, mỗi truy vấn cho bởi hai số (u,v) thể hiện: Đang ở tại nhà thứ \(u\) và di chuyển từ tòa nhà thứ \(u\) sang nhà thứ \(v\) sao cho mất ít năng lượng nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n,Q(2≤n≤10^5;1≤Q≤10^5 ) \)

• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2,..., h_n (1≤h_i≤10^9 )\)

• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v(1≤u,v≤n;u≠v)\) (Chú ý rằng \(u\) có thể lớn hơn \(v\))

Output

• Gồm \(Q\) dòng, mỗi dòng ứng với kết quả của truy vấn tương ứng.

Sample Input

7 6
14 82 9 6 8 12 7
1 3
1 7
4 6
7 1
3 5
4 2

Sample Output

73
81
0
74
3
0