|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
<div style="text-align: justify">There is a sequence of integers $c_1, c_2, \ldots, c_k$. This sequence was hidden, by constructing a new sequence $b_1, b_2, \ldots, b_{k-1}$ according to the following rule: each element $b_i$ is equal to the sum of $c_i$ and $c_{i+1}$ (i.e., $b_i=c_i+c_{i+1}$) for all $i$ from $1$ to $k-1$.Your task is to determine the maximum number of distinct numbers that can be in the original sequence $c_1, c_2, \ldots, c_k$, given the values of $b_1, b_2, \ldots, b_{k-1}$.To make the task more challenging for reconstructing the sequence $c$, you receive an array $a_1, a_2, \ldots, a_n$. You need to process $m$ queries in the form of intervals $[l, r]$, where $l$ and $r$ are some indices of elements in the sequence $a$. For each query, you are required to determine the number of distinct numbers in the sequence $c$ if the sequence $b$ were equal to $a_l, a_{l+1}, \ldots, a_r$. </div>There is a sequence of integers $c_1, c_2, \ldots, c_k$. This sequence was hidden, by constructing a new sequence $b_1, b_2, \ldots, b_{k-1}$ according to the following rule: each element $b_i$ is equal to the sum of $c_i$ and $c_{i+1}$ (i.e., $b_i=c_i+c_{i+1}$) for all $i$ from $1$ to $k-1$.
Your task is to determine the maximum number of distinct numbers that can be in the original sequence $c_1, c_2, \ldots, c_k$, given the values of $b_1, b_2, \ldots, b_{k-1}$.
To make the task more challenging for reconstructing the sequence $c$, you receive an array $a_1, a_2, \ldots, a_n$. You need to process $m$ queries in the form of intervals $[l, r]$, where $l$ and $r$ are some indices of elements in the sequence $a$. For each query, you are required to determine the number of distinct numbers in the sequence $c$ if the sequence $b$ were equal to $a_l, a_{l+1}, \ldots, a_r$.
Input
<div style="text-align: justify">In the first line, two integers $n$ and $m$ $(1 \leq n \leq 2\cdot 10^5, 1 \leq m \leq 2\cdot 10^5)$ are entered - the size of the sequence $a$ and the number of queries, respectively.In the second line, $n$ integers $a_1, a_2, \ldots, a_n$ $(-10^9 \leq a_i \leq 10^9)$ are entered - the elements of the sequence $a$.Then, $m$ lines follow, each containing two integers $l$ and $r$ $(1 \leq l \leq r \leq n)$ - the starting and ending indices of the interval for each query. </div>In the first line, two integers $n$ and $m$ $(1 \leq n \leq 2\cdot 10^5, 1 \leq m \leq 2\cdot 10^5)$ are entered - the size of the sequence $a$ and the number of queries, respectively.
In the second line, $n$ integers $a_1, a_2, \ldots, a_n$ $(-10^9 \leq a_i \leq 10^9)$ are entered - the elements of the sequence $a$.
Then, $m$ lines follow, each containing two integers $l$ and $r$ $(1 \leq l \leq r \leq n)$ - the starting and ending indices of the interval for each query.
Output
<div style="text-align: justify">For each query, output in a separate line the number of distinct numbers in the sequence $c$ if the sequence $b$ were equal to $a_l, a_{l+1}, \ldots, a_r$. </div>For each query, output in a separate line the number of distinct numbers in the sequence $c$ if the sequence $b$ were equal to $a_l, a_{l+1}, \ldots, a_r$.
Sample test(s)
Input
10 7
0 0 1 2 10 11 3 101 109 55
1 10
3 10
2 4
1 9
2 5
3 6
6 10
Output
8
7
4
7
5
5
5
Input
15 10
10 0 -9 3 3 4 6 -6 -4 -4 -11 -1 1 -2 0
3 10
3 12
5 6
3 15
10 15
6 6
3 5
1 1
12 14
4 10
Output
7
9
3
12
7
2
3
2
4
6
Hints
* If $b = [1, 2, 3]$, then $c$ might be equal to [$2, -1, 3, 0$].* If $b = [0]$, then $c$ might be equal to [$1000, -1000$].- If $b = [1, 2, 3]$, then $c$ might be equal to [$2, -1, 3, 0$].
- If $b = [0]$, then $c$ might be equal to [$1000, -1000$].