题目描述

薯条哥有一个数组，他想知道有多少连续子数组的和同时是$3$和$5$的倍数，但不是$4$的倍数。

输入描述

第一行输入一个整数 $n(1\le n\le 10^5)$表示数组长度。

第二行输入$n$个整数表示数组 $a_i(1\le a_i\le 10^9)$

输出描述

输出一个整数。

样例

输入

3
13 17 30

输出

2