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!!!