Fibus

Cerință

Se dă un șir $a$ format din $n$ numere naturale. Câte subsecvențe ale acestui șir sunt subsecvențe și ale șirului lui fibonacci?

O subsecvență a unui șir $a_1,a_2,\ldots,a_n$ cu capetele în $a_l$ și $a_r$ ($1 \le l \le r \le n$) conține elementele $[a_l,a_{l+1},a_{l+2},\ldots,a_{r-1},a_r]$.

Date de intrare

Pe prima linie a fișierului de intrare fibus.in se va afla $n$ - lungimea șirului $a$.

Pe a doua linie se vor afla $n$ numere $a_1,a_2,\ldots,a_n$ - elementele șirului $a$.

Date de ieșire

Fișierul de ieșire fibus.out va conține numărul de subsecvențe ale șirului $a$ care sunt și subsecvențe ale șirului lui fibonacci.

Restricții și precizări

• $1 \le n \le 3 \cdot 10^5$
• $1 \le a_i \le 10^9$

  #	Punctaj	Restricții
  1	15	$a_1=a_2=\ldots=a_n$
  2	30	$n \le 100$
  4	20	$n \le 1000$
  5	35	Fără restricții suplimentare

Exemplul 1

fibus.in

7
1 1 1 2 3 4 1

fibus.out

13

Explicație

Cele $13$ subsecvențe care sunt subsecvențe și ale șirului lui fibonacci sunt: $[a_1]$, $[a_2]$, $[a_3]$, $[a_4]$, $[a_5]$, $[a_7]$, $[a_1,a_2]$, $[a_2,a_3]$, $[a_3,a_4]$, $[a_4,a_5]$, $[a_2,a_3,a_4]$, $[a_3,a_4,a_5]$ și $[a_2,a_3,a_4,a_5]$.

Exemplul 2

fibus.in

2
1 3

fibus.out

2

Explicație

Cele $2$ subsecvențe care sunt subsecvențe și ale șirului lui fibonacci sunt $[a_1]$ și $[a_2]$.