{"code":"incqueries","name":"INCQUERIES","description":"Cho một dãy $N$ số nguyên dương $A_1,A_2,…,A_N$. Một thao tác thay đổi là việc chọn một phần tử $a_i (1\\leq i \\leq N)$ và thay thế $A_i=A_i+1$.\r\n\r\n**Yêu cầu**: Bạn cần trả lời $q$ truy vấn. Mỗi truy vấn cho bạn một dãy con liên tiếp trong đoạn từ $l\\rightarrow r$ và yêu cầu tính xem số lượng thao tác thay đổi tối thiểu để cho dãy con đã cho thành dãy không giảm.\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa hai số nguyên dương $N,q$ $(1\\leq N,q \\leq 2 \\times 10^5)$;\r\n- Dòng tiếp theo gồm $N$ số nguyên dương $A_1,A_2,…,A_n$ $(A_i\\leq 10^9)$.\r\n- $q$ dòng cuối cùng, mỗi dòng gồm 2 số nguyên dương $l, r$ $(1\\leq l \\leq r \\leq n)$ biểu thị cho dãy con từ $l$ đến $r$.\r\n\r\n\r\n

Output

\r\n\r\n- In ra $q$ dòng, mỗi dòng chứa một số nguyên không âm là kết quả bài toán của truy vấn tương ứng.\r\n\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 3\r\n 2 10 4 2 5\r\n 3 5\r\n 2 2\r\n 1 4\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n 0\r\n 14\r\n ```\r\n \r\n ??? warning \"Note\"\r\n \r\n - Truy vấn đầu tiên, bạn có thể sử dụng 2 thao tác để chuyển dãy con đã cho từ $[4,2,5]$ thành $[4,4,5]$.\r\n - Truy vấn thứ 2, dãy con đã cho là dãy không giảm nên không cần thực hiện thao tác thay đổi nào.\r\n - Trong truy vấn thứ 3, bạn có thể sử dụng 14 thao để chuyển dãy con thành $[2,10,10,10]$.","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}