Domino

AtCoder

IDabc435_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ dominoes standing in a row on a number line. The $i$\-th domino is standing at coordinate $i$ and has height $A_i$. When the $i$\-th domino falls to the right, all dominoes in the range between coordinates $i$ and $i+A_i-1$, inclusive, fall to the right. How many dominoes will fall in total when the first domino falls to the right? ## Constraints * $1\leq N \leq 5\times 10^5$ * $1\leq A_i \leq N$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

4
3 1 4 1

Output #1

4

When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.

Input #2

9
1 4 1 4 2 1 3 5 6

Output #2

1

When the first domino falls to the right, no other dominoes will fall.

Input #3

10
5 4 3 2 1 1 2 3 4 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Domino",
    "description": {
      "content": "There are $N$ dominoes standing in a row on a number line. The $i$\\-th domino is standing at coordinate $i$ and has height $A_i$. When the $i$\\-th domino falls to the right, all dominoes in the range ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc435_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ dominoes standing in a row on a number line. The $i$\\-th domino is standing at coordinate $i$ and has height $A_i$.\nWhen the $i$\\-th domino falls to the right, all dominoes in the range ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments