There \(is\) \(a\) new bakery \(in\) town! Come and try delicious cakes from Dodo’s bakery!
The bakers have prepared \(n\) cakes, the \(i-th\) of which has sweetness \(a@@RISE_MATH_BLOCK_0@@i\) cakes whose sweetnesses are at least \(s\)\(i\)”.
Dorijan serves customers in a peculiar way. He will give \(d_{i}\) continuous cakes from
the table. To keep the table looking as nice as possible he will only give cakes from
the left or the right edge of the table. He noticed that he cannot serve a lot of customers that way, so
before serving a customer he will eat some cakes (possibly none) from the edges of the table.
If Dorijan cannot satisfy a customer, he will close the bakery for the day. What is the largest number of
customers he can serve, before closing?

Subtask 1 (21 points): n, \(q \le 100\)

Subtask 2 (31 points): \(d@@RISE_MATH_BLOCK_0@@q = 1\)

Subtask 3 (58 points): No additional constraints.

The first line contains two integers n, q (\(1 \le n \le 5\,000\), \(1 \le q \le 2 \cdot 10^{5}\)), the number of cakes and the
number of people in the line.
The second line contains \(n\) numbers \(a_{i}\) (\(1 \le a_{i} \le 10^{9}\)), where \(a_{i}\) is the sweetness of the \(i-th\) cake.
In each of the next \(q\) lines there are two integers \(d@@RISE_MATH_BLOCK_0@@i\) (\(1 \le d@@RISE_MATH_BLOCK_1@@i \le 10^{9}\)), the order of the \(i-th\)
customer in line.

In the first and only line output the number of customers Dorijan can serve.

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 5