G. Count the Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, \dots, a_n$$$. Your task is to count the number of pairs $$$1 \leq i \lt j \leq n$$$ for which $$$\gcd(a_i + j, a_j + i) = i + j$$$.

Input

The first contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 2\cdot 10^5$$$) — elements of array $$$a$$$.

Output

Output the number of pairs that satisfy the condition.

Examples
Input
6
13 20 11 16 11 5
Output
4
Input
5
1 2 3 4 5
Output
10
Note

In the first sample, there are four pairs:

  • $$$[\color{orange}{13}, \color{orange}{20}, 11, 16, 11, 5]$$$, where $$$\gcd(13+2,20+1)=1+2$$$.
  • $$$[\color{orange}{13}, 20, \color{orange}{11}, 16, 11, 5]$$$, where $$$\gcd(13+3,11+1)=1+3$$$.
  • $$$[\color{orange}{13}, 20, 11, 16, \color{orange}{11}, 5]$$$, where $$$\gcd(13+5,11+1)=1+5$$$.
  • $$$[13, \color{orange}{20}, 11, \color{orange}{16}, 11, 5]$$$, where $$$\gcd(20+4,16+2)=2+4$$$.

In the second sample, each pair satisfies the condition.