CF2206E Parallel Sums

You are given two integers $ n $ and $ m $ . For a sequence of $ n $ integers $ A=(a_1, a_2, \ldots, a_n) $ , the parallel sums of $ A $ are the $ n-m+1 $ integers $ s_1, s_2, \ldots, s_{n-m+1} $ defined by $ s_i = a_i + a_{i+1} + \ldots + a_{i+m-1} $ for each $ i $ ( $ 1 \leq i \leq n-m+1 $ ). You are given the values of $ s_1, s_2, \ldots, s_{n-m+1} $ . Your task is to answer $ q $ queries, described as follows. In the $ j $ -th query, you are given two integers $ l_j $ and $ r_j $ , and you are asked to find the smallest possible value of $ \max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}) $ among all sequences $ A=(a_1, a_2, \ldots, a_n) $ of $ n $ integers (possibly negative) such that $ s_1, s_2, \ldots, s_{n-m+1} $ are the parallel sums of $ A $ . Or determine if this value can be arbitrarily small.

The first line of input contains two integers $ n $ and $ m $ ( $ 1 \leq m \leq n \leq 200\,000 $ ). The second line contains $ n-m+1 $ integers $ s_1, s_2, \ldots, s_{n-m+1} $ ( $ -10^9 \leq s_i \leq 10^9 $ ). The third line contains a single integer $ q $ ( $ 1 \leq q \leq 100\,000 $ ). The $ j $ -th of the next $ q $ lines contains two integers $ l_j $ and $ r_j $ ( $ 1 \leq l_j \leq r_j \leq n $ ).

Output $ q $ lines. The $ j $ -th line should contain the smallest possible value of $ \max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}) $ . If that value can be arbitrarily small, output unbounded instead.

Explanation for the sample input/output #1 For the first query, take $ A = (9, -4, -3, 2, 1, 2, 1, 1) $ . The parallel sums of $ A $ are $ (4, -4, 2, 6, 5) $ as required. Then $ \max(a_3, \ldots, a_7) = \max(-3, 2, 1, 2, 1) = 2 $ . It can be shown that $ 2 $ is the smallest possible value. For the second query, you can make the value arbitrarily small. For the third query, take $ A = (4, -3, 0, 3, -4, 3, 4, 2) $ . Then $ \max(4, -3, 0, 3, -4, 3, 4, 2) = 4 $ , which is the smallest possible value.