Thành phố \(X\) có \(n\) tòa nhà, và tòa nhà thứ \(i\) có chiều cao \(a_i\)
Bây nhờ bạn có \(m\) nhiệm vụ cần thực hiện, cụ thể như sau:
++ Nhiệm vụ thứ \(j\) được biểu diễn bởi hai số nguyên \(s_j\) và \(t_j\).
++ Ở nhiệm vụ này, bạn phải di chuyển từ tòa nhà thứ \(s_j\) sang tòa nhà thứ \(t_j\)
++ Khi bắt đầu nhiệm vụ, bạn đã có mặt sẵn ở tòa nhà thứ \(s_j\)

Ở mỗi lần di chuyển, bạn chỉ có thể di chuyển từ cột thứ \(x\) sang cột thứ \(x-1\) hoặc cột thứ \(x+1\). Nhưng may mắn thay, nhân dịp đầu năm, bạn được vị thần cai quản thành phố \(X\) tên là Lucii 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 \(a_p>a_q\), thì bạn sẽ bị mất đi \(a_p-a_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.

Ứng với mỗi nhiệm vụ được giao, bạn hãy xác định năng lượng tối thiếu để hoàn thành nhiệm vụ và in giá trị này ra màn hình

Input

• Dòng đầu tiên chứa hai số nguyên \(n,m(2\le n\le 10^5; 1\le m\le 10^5)\) - Thể hiện số tòa nhà trong thành phố \(X\) và số lượng nhiệm vụ mà bạn phải hoàn thành.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^9)\) - Thể hiện chiều cao của tòa nhà thứ \(i\)
• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(s_j\) và \(t_j(1\le s_j,t_j\le n; s_j\ne t_j)\)
  (Chú ý rằng \(s_j\) có thể lớn hơn \(t_j\))

Output

• Ứng với nhiệm vụ, hãy in kết quả ra màn hình

Example

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

73
81
0
74
3
0