{"code":"naixuinterval","name":"Chia đoạn nai-sừ","description":"Một dãy số nguyên có $k$ phần tử $a_1,a_2,...,a_k$ được gọi là dãy nai-sừ khi $k=1$ hoặc nó là một dãy số nguyên liên tiếp, hay: $a_{i}+1=a_{i+1}(1\\le i<k)$\r\nCho một dãy số nguyên $a$ có $n$ phần tử và một số nguyên dương $k$. Trong một thao tác, ta có thể chọn một phần tử $a_i$ và tăng hoặc giảm phần tử đó đi $1$ đơn vị. Một cách chia đoạn của dãy $a$ được gọi là nai-sừ khi:\r\n + Mỗi phần tử của dãy $a$ thuộc vào đúng một đoạn\r\n + Gọi chi phí của một đoạn là số lần thao tác ít nhất để đưa đoạn đó trở thành dãy nai-sừ thì mọi chi phí của các đoạn được chia đều không vượt quá $k$\r\n + Số đoạn được chia là ít nhất có thể\r\n\r\nCó $q$ truy vấn, mỗi truy vấn cho hai số nguyên dương $l,r(1\\le l\\le r\\le n)$, bạn cần trả lời số đoạn được chia trong cách chia đoạn nai-sừ của dãy con liên tiếp $a_l,a_{l+1},...,a_r$\r\n\r\n#### Input\r\n - Dòng $1$ chứa ba số nguyên dương $n,k,q(1\\le n,q\\le 10^5, 1\\le k\\le 10^{16})$\r\n - Dòng $2$ chứa $n$ số nguyên $a_1,a_2,...,a_n(|a_i|\\le 10^9 \\forall i\\in [1;n])$\r\n - $q$ dòng tiếp theo, mỗi dòng có hai số nguyên dương $l,r(1\\le l\\le r\\le n)$\r\n#### Output\r\n- Gồm $q$ dòng, dòng thứ $i$ chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ $i$\r\n\r\n#### Scoring\r\n - Subtask $1$ ($10$% số điểm): $n,q\\le 10$\r\n - Subtask $2$($15$% số điểm): $q=1,n\\le 1000$\r\n - Subtask $3$($15$% số điểm): $q=1,n\\le 10^5$\r\n - Subtask $4$($20$% số điểm):$n,q\\le 1000$\r\n - Subtask $5$($40$% số điểm): Không có ràng buộc gì thêm\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        8 4 3\r\n        2 5 8 4 7 10 4 6 \r\n        1 8\r\n        3 7\r\n        2 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        3\r\n        2\r\n        ```\r\n#### Note\r\n - Truy vấn $1$, chia dãy thành các đoạn như sau: $[2,4,8][4,7,10][4,6]$\r\n - Truy vấn $2$, chia dãy thành các đoạn như sau: $[8][4,7,10][4]$\r\n - Truy vấn $3$, chia dãy thành các đoạn như sau: $[5,8][4,7]$","points":2200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}