Problem B
1-D Frogger (Hard)

Image by alptraum (iStock); Used under license

Frogger is a classic $2$-D video game that challenges the player to move a frog character safely across a traffic-filled road and a hazardous river. What is not well known is that Frogger actually began as a prototype board game based on a $1$-D concept at a now-defunct toy company.¹ After spending millions of dollars following the advice of consultants, company executives realized that the resulting game was almost completely deterministic, and therefore not much fun to play,² so they sold all Frogger rights to a video game company in an attempt to recoup some of the development costs. The rest, as they say, is video game history.

The original $1$-D Frogger design, however, makes for good programming competition problems. Here is how the game works. The board is a row of $n$ squares, each of which contains a non-zero integer. These squares are indexed $1, 2, \ldots , n$, from left to right. To start the game, the player rolls an $n$-sided die with one of the distinct indices on each side, and places a frog token on the board square with the resulting index. The player then randomly selects a card from a deck of cards with integers written on them (one per card); the integer on each card is contained in at least one board square. The number on the selected card is the magic number (or goal number) for this instance of the game.

The player then applies the following rule as many times as necessary until the game ends:

• If the frog is on a square containing a positive integer, $k$, the frog makes a length-$k$ hop to the right. (Hop distance is measured in board square units.)

• If the frog is on a square containing a negative integer, $k$, the frog makes a length-$|k|$ hop to the left (note the absolute value).

The game ends as soon as the frog encounters one of the following four fates:

1. The frog lands on a square containing the magic number. This is the only winning outcome for the player. Note that if the frog starts on a square containing the magic number, the player wins immediately (i.e., after $0$ hops).

2. The frog falls off the left end of the board.

3. The frog falls off the right end of the board.

4. The frog hops onto a square where the frog has been before, and therefore is trapped in a cycle.

For a given Frogger board, if $s$ is the frog’s starting position and $m$ is the magic number, then the pair $(s,m)$ is a winning instance if the game ends with the frog landing on a square containing $m$. Your challenge is to count the number of winning instances.

Input

The input is the description of a Frogger board. The first line contains an integer, $n$, the number of board squares $(1 \leq n \leq 200\, 000)$. This is followed by a line containing $n$ space-separated non-zero integers. These are the numbers in the board squares in order from left to right. Each board square number is in the interval $[-200\, 000, 200\, 000]$.

Output

Output a single integer: the number of winning instances.

4
1 2 3 4

7

2
1 -1

4