The Missing Cat Shortcut

Time limit: 2000 msMemory limit: 256 MB

Along a straight rooftop, $N$ cats stand at distinct positions $X_1, X_2, \ldots, X_N$ , listed from left to right. Cat $i$ has jump power $D_i$ .

Cat $i$ can jump directly to cat $j$ on its right if and only if

$X_j-X_i \le D_i.$

A relay surprise is an ordered triple of indices $(a,b,c)$ satisfying $1 \le a<b<c \le N$ for which:

cat $a$ can jump directly to cat $b$ ;
cat $b$ can jump directly to cat $c$ ; and
cat $a$ cannot jump directly to cat $c$ .

Count the number of relay surprises.

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of cats.

The next $N$ lines describe the cats in left-to-right order. The -th of these lines contains two integers and (, ), the position and jump power of cat .

Output

Print one integer: the number of relay surprises.

Samples

Sample 1

Input

Output

The relay surprises are $(1,2,4)$ and $(2,4,5)$ .

Sample 2

Input

Output

Every earlier cat can jump directly to every later cat, so there are no relay surprises.

The Missing Cat Shortcut

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions