P10700 [SNCPC2024] Guess Primes II

To secretly prepare a mysterious prime number, MCPlayer542 racked his brains. Then he invented a ~~clever~~ stupid method and named it “Prime Score”. He prepared $n$ distinct numbers $a_1,\ a_2,\ \ldots,\ a_n$ as test points, and defined the “Prime Score” $score(x,l,r)$ as follows: $$score(x,l,r)=\sum_{i=l}^r{f(x,a_i)}$$ where $$f(x,y)=\left\{\begin{array}{rcl}u-y, & x=1 \\ u, & 1

The first line of the input contains two integers $n,\ q$ ($1\le n,\ q\le 5\times 10^5$), separated by a single space. The second line contains $n$ integers $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$), separated by single spaces, representing the testdata of the test points. The next $q$ lines each contain two integers $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$), separated by a single space, representing one query.

For each query, output one line with two numbers: the maximum total score for the query and the smallest $r_i$ ($l_i\le r_i\le n$) that can achieve this score, separated by a single space.

In the first query of Sample 1, $u_1=14,\ l_1=4$. If we choose $r_1=6$, then the final total score is $\sum_{i=1}^{10^6}{score(i,4,6)}$. Here: - $score(1,4,6)=13+9+11=33$; - $score(2,4,6)=0+14+14=28$; - $score(3,4,6)=0+14-9=5$; - $score(4,4,6)=0+14+0=14$; - $score(5,4,6)=0-25+0=-25$; - for other values of $i$, we have $score(i,4,6)=0+0+0=0$. Therefore, when $r_1=6$ the total score is $33+28+5+14-25=55$. It can be proven that no larger total score can be obtained for other values of $r_1$. Therefore the answer is $55$, and the smallest $r_1$ that achieves it is $6$. Translated by ChatGPT 5