Hôm nay là một ngày rất tuyệt vời đối với ShyWoou, anh ấy cho bạn một dãy số gồm \(N\) phần tử \(a_1, a_2, ..., a_{N}\), trong một thao tác, anh ấy có thể:

• Chọn bất kì một đoạn \([L, R]\) \((1 \leq L \leq R \leq N)\)\(;\)
• Cộng \(1\) vào \(a_{L}\), trừ \(1\) vào \(a_{L + 1}\), cộng \(1\) vào \(a_{L + 2}\), \(...\) lặp lại thao tác liên tục cho đến \(a_{R}\).

ShyWoou có \(Q\) thao tác, thao tác thứ \(i\) thực hiện trên đoạn \([L_{i}, R_{i}]\) và anh ấy yêu cầu bạn hãy tính tổng của mảng sau khi thực hiện \(Q\) thao tác trên.

Input

• Dòng đầu tiên gồm số nguyên \(N, Q\) \((N \leq 10^5, Q \leq 10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, ..., a_{N}\) \((a_{i} \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên dương \(L_{i}, R_{i}\) \((1 \leq L_{i} \leq R_{i} \leq N)\).

Output

• Một dòng duy nhất là tổng của mảng sau khi thực hiện \(Q\) thao tác.

Sample Input

5 2
1 2 3 4 5
2 4 
1 3

Sample Output

17

Giải thích

• Dãy số sau khi thực hiện thao tác thứ \(1\): \([1, \space 3, \space 2, \space 5, \space 5];\)
• Dãy số sau khi thực hiện thao tác thứ \(2\): \([2, \space 2, \space 3, \space 5, \space 5];\)
• Tổng của mảng sau khi thực hiện \(2\) thao tác là: \(2 + 2 + 3 + 5 + 5 = 17\)

Subtask

• \(30\%\) số test đầu tiên có \(N \leq 10^3, Q \leq 10^3\).
• \(70\%\) số test còn lại có \(N \leq 10^5, Q \leq 10^5\).