Given a graph of $$$N$$$ nodes . Each node $$$i$$$ has value $$$A[i]$$$ . There is a directed edge from node $$$i$$$ to node $$$j$$$ if $$$A[i]\ >\ A[j]$$$ and $$$|i-j|\ \le\ K$$$ .

For every element , $$$B[i]$$$ is shortest distance to a node with prime value , if there is no path to such node $$$B[i]\ =\ 0$$$ . Find the sum of all elements of $$$B$$$ modulo $$$10^9\ +\ 7$$$ .

Constraints :

$$$1 \le K\le N\ \le 10^5\newline $$$ $$$B[i]\le\ 10^6\ \ \ \ \forall\ 1 \le i \le N$$$

Example :

• $$$N=1 \ , K=1 \ , A = [1]\newline$$$ $$$B = [0]\ , sum = 0\newline$$$
• $$$N=3 \ , K=1 \ , A = [1,2,4]\newline$$$ $$$B = [0,0,1] \ , sum = 1\newline$$$
• $$$N=5 \ , K=2 \ , A = [2,4,8,16,32]\newline$$$ $$$B = [0,1,1,2,2] \ , sum = 6\newline$$$

Note : This question was asked in an on-campus coding exam & it was completed

Given an array $$$A$$$ of $$$N$$$ integers . Find the maximum of value of $$$i\ -\ j$$$ such that : $$$\newline$$$ $$$1)\ j\ \le\ i \newline$$$ $$$2)\ A[j]\ \le\ A[i] \newline$$$

Note : $$$i$$$ and $$$j$$$ are 0-based indices

Constraints :
$$$ N \le 10^6\ ;\ A[i]\ \le\ 10^9\ for\ 0\ \le i\ \le\ N-1\newline $$$

Ex :

• $$$A\ =\ [1,2,3,4,5]$$$
  $$$j\ =\ 0\ ,\ i\ =\ 4$$$ gives maximum difference of 4 satisfying the given conditions




• $$$A\ =\ [8,4,8,7,6,6,3]$$$
  $$$j\ =\ 1\ ,\ i\ =\ 5$$$ gives maximum difference of 4 satisfying the given conditions

Note : This question was asked in an on-campus coding exam & it was completed

Forgive me for the English & formatting.