{"code":"2024usopenplatinum2","name":"USACO 2024 US Open Contest, Platinum, Splitting Haybales","description":"Nông dân John muốn chia đều cỏ giữa hai con bò yêu thích của mình là Bessie và Elsie. Anh có $N$ ($1 \\leq N \\leq 2 \\times 10^5$) bó cỏ được sắp xếp theo thứ tự không tăng dần, trong đó bó cỏ thứ $i$ có $a_i$ cọng cỏ ($2 \\times 10^5 \\geq a_1 \\geq a_2 \\geq ...  \\geq a_N \\geq1$).\r\n\r\nNông dân John đang nghĩ đến chuyện chia những bó cỏ một cách lần lượt cho hai con bò, cụ thể như sau:\r\n- Nông dân John chia các bó cỏ theo đúng thứ tự từ $l$ đến $r$ trong kho cỏ cho trước. \r\n- Với bó cỏ thứ $i$, anh John sẽ đưa cho con bò có ít cỏ hơn. Nếu 2 con bò cố lượng cỏ bằng nhau, anh John sẽ đưa cho Bessie.\r\n\r\nBạn được cho Q truy vấn ($1 \\leq Q \\leq 2 \\times 10^5$), mỗi truy vấn gồm 3 số nguyên $l, r, x$ ($1 \\leq l \\leq r \\leq N, |x| \\leq 10^9$). Với mỗi truy vấn, bạn cần tìm xem Bessie sẽ có nhiều hơn Elsie bao nhiêu cọng cỏ, biết Bessie ban đầu có nhiều hơn Elsie $x$ cọng cỏ. Lưu ý rằng giá trị này âm nếu Elsie có nhiều cỏ hơn Bessie.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa $N$.\r\n- Dòng thứ hai chứa $a_1…a_N$.\r\n- Dòng thứ ba chứa $Q$.\r\n- $Q$ dòng tiếp theo chứa $l, r, x$.\r\n\r\n#### Output\r\n\r\n- Gồm $Q$ dòng, mỗi dòng chứa câu trả lời cho mỗi truy vấn.\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$: $Q \\leq 100$\r\n- Subtask $2$: Tối đa $100$ giá trị $a_i$ khác nhau\r\n- Subtask $3$: Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2\r\n        3 1\r\n        15\r\n        1 1 -2\r\n        1 1 -1\r\n        1 1 0\r\n        1 1 1\r\n        1 1 2\r\n        1 2 -2\r\n        1 2 -1\r\n        1 2 0\r\n        1 2 1\r\n        1 2 2\r\n        2 2 -2\r\n        2 2 -1\r\n        2 2 0\r\n        2 2 1\r\n        2 2 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        2\r\n        3\r\n        -2\r\n        -1\r\n        0\r\n        1\r\n        2\r\n        -1\r\n        0\r\n        -1\r\n        0\r\n        1\r\n        0\r\n        1\r\n        ```\r\n    ??? warning \"Note\"\r\n        \r\n        - Đối với truy vấn đầu tiên, Elsie ban đầu có nhiều hơn Bessie $2$ cọng cỏ. Sau đó, sau khi xử lý bó cỏ thứ $1$, Bessie sẽ nhận được $3$ cọng cỏ, và Bessie sẽ có nhiều hơn Elsie $1$ cọng cỏ.\r\n        - Đối với truy vấn thứ $3$, Elsie và Bessie ban đầu có cùng số lượng cỏ. Sau khi xử lý bó cỏ thứ $1$, Bessie sẽ nhận được $3$ cọng cỏ, và Bessie sẽ có nhiều hơn Elsie $3$ cọng cỏ.\r\n        - Đối với truy vấn thứ $9$, Bessie ban đầu có nhiều hơn Elise $1$ cọng cỏ. Sau khi xử lý bó cỏ thứ $1$, Bessie có ít hơn Elsie $2$ cọng cỏ, và sau khi xử lý bó cỏ thứ $2$, Bessie có ít hơn Elsie $1$ cọng cỏ.      \r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        4 4 3 1 1\r\n        7\r\n        1 1 20\r\n        1 2 20\r\n        1 5 20\r\n        1 1 0\r\n        1 5 0\r\n        1 4 0\r\n        3 5 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        16\r\n        12\r\n        7\r\n        4\r\n        1\r\n        2\r\n        1\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Trong truy vấn thứ $5$, có $5$ bó cỏ. Bessie nhận được $4$ cọng cỏ, sau đó Elsie nhận được $4$ cọng cỏ, sau đó Bessie nhận được $3$ cọng cỏ, sau đó Elsie nhận được $1$ cọng cỏ, sau đó Elsie nhận được $1$ cọng cỏ.","points":1000.0,"partial":true,"time_limit":2.0,"memory_limit":256,"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}}