Problem Description

Given a sequence $[a_1,a_2,a_3,\dots,a_n]$, it is guaranteed that $\forall i\in [2,n], a_i\ge a_{i-1}$.

Compute how many integer triples $(i,j,k)$ satisfy:

• $1\le i,j,k\le n$.
• $a_i\times j\times a_k=i+a_j+k$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$. It is guaranteed that $a_i\ge a_{i-1}$.

Output Format

Output one line with one non-negative integer, which is the answer.

5
2 3 3 4 5

3

10
1 1 2 2 3 3 4 4 5 8

25

Hint

This problem has three subtasks.

All testdata satisfy: $1\le n\le 10^6$, $1\le a_i\le 10^6$, $a_i\ge a_{i-1}$.

• Subtask $1$ ($5$ points): $n\le 500$.
• Subtask $2$ ($5$ points): $a_i\le 10$.
• Subtask $3$ ($90$ points): no special constraints.

Translated by ChatGPT 5