I encountered this problem in a previous coding round at a Dare2Compete challenge.
The problem goes like this...
We are given a sequence of N integers X[1], X[2]....X[N].
A beautiful sequence A[1], A[2], .....A[N] is the one following both of the conditions :
1 <= A[i] <= X[i]
A[i] ≠ A[i+1] (1 <= i < N)
Count the number of beautiful sequences modulo any prime number. (let's say 1000000007)
Constraints:
1 <= X[i] <= 1e9
2 <= N <= 5e5
Example test case —
Inputs : N = 3, X = {2, 3, 2}
Output : 6
I tried solving it but wasn't able to do it. Please guide me in this question.
Also, I want to practice these types of questions where conditions for adjacent elements are given, like this. Thus it will be a great help if you put on the links of such questions in the comments.
Link
Oh god!
Thank you soooo much!!!