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. 1 <= A[i] <= X[i]
2. 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.