[Solution] Placing Jinas Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Placing Jinas Codeforces Solution | Codeforces Problem Solution 2022

E. Placing Jinas

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

We say an infinite sequence a0,a1,a2,…$a_0,a_1,a_2,\dots$ is non-increasing if and only if for all i≥0$i\ge 0$, ai≥ai+1$a_i\ge a_{i+1}$.

There is an infinite right and down grid. The upper-left cell has coordinates (0,0)$(0,0)$. Rows are numbered 0$0$ to infinity from top to bottom, columns are numbered from 0$0$ to infinity from left to right.

There is also a non-increasing infinite sequence a0,a1,a2,…$a_0,a_1,a_2,\dots$. You are given a0$a_0$, a1$a_1$, …$\dots$, an$a_n$; for all i>n$i>n$, ai=0$a_i=0$. For every pair of x$x$, y$y$, the cell with coordinates (x,y)$(x,y)$ (which is located at the intersection of x$x$-th row and y$y$-th column) is white if y<ax$y<a_x$ and black otherwise.

Initially there is one doll named Jina on (0,0)$(0,0)$. You can do the following operation.

• Select one doll on (x,y)$(x,y)$. Remove it and place a doll on (x,y+1)$(x,y+1)$ and place a doll on (x+1,y)$(x+1,y)$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Note that multiple dolls can be present at a cell at the same time; in one operation, you remove only one. Your goal is to make all white cells contain 0$0$ dolls.

What's the minimum number of operations needed to achieve the goal? Print the answer modulo 109+7${10}^9+7$.

Input

The first line of input contains one integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$).

NIT orz! Codeforces Solution

NIT Destroys the Universe Codeforces Solution 

Fishingprince Plays With Array Codeforces Solution

Permutation Graph Codeforces Solution

Placing Jinas Codeforces Solution 

Tree Recovery Codeforces Solution

Fishingprince Plays With Array Again Codeforces Solution

Maximum Product? Codeforces Solution

The second line of input contains n+1$n+1$ integers a0,a1,…,an$a_0,a_1,\dots ,a_n$ (0≤ai≤2⋅105$0\le a_i\le 2\cdot {10}^5$).

It is guaranteed that the sequence a$a$ is non-increasing.

Output

Print one integer — the answer to the problem, modulo 109+7${10}^9+7$.