Hello CodeForces How to find minimal prime divisor for n <= 10^12 if there are number of queries <= 10^5

Hi CodeForces, help me please with this -> problem

I tryed to use BFS, but i got TLE

Hi CodeForces.

I won't give link of problen and explain statement of problem, because this problem has more easier solution. But i want implement my solution idea, but i have problems with realization, and i need your help.

In problem i must calculate dp

for (int i = 1; i <= n; i++){
  int mn = inf, mx = -inf;
  for (int j = i; j >= 1; j--){
    mn = min(mn, a[j]), mx = max(mx, a[j]);
    dp[i] = max(dp[i], dp[j - 1] + (mx - mn));
  }
}

Problem can not be solved in O(N^2), because N <= 10^6

I think, exist way to calculate dp mush faster -> dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) 1 <= j < i

mx[j] -> maximum from j to i

mn[j] -> minimum from j to i

Thanks in advance!

Where is editorial from author???

Can you explain soluton idea with treap?

Hello CodeForces. Offensively that round #383 was rescheduled.

Please help me with this problem.

#CFstayalive

Ladies and Gentlemen, please help me -> problem.