题目描述

薯条哥是一位热爱数学和计算机科学的年轻人。他一直喜欢思考各种有趣的问题，并利用自己的知识和技能来解决它们。现在薯条哥有一个正整数数组 $A$ ，他想玩一个游戏，找出数组中有多少个连续的子数组，满足以下条件： 子数组中的所有数字相乘的结果和相异或的结果相等。

每有一个满足条件的子数组即得一分，问薯条哥最多能得到多少分？

一个数组的子数组指数组中非空的一段连续数字。

输入描述

第一行一个正整数 $n(1\le n\le 10^5)$，代表给出数组长度

第二行 $n$ 个空格分隔的正整数 $A_i(1\le A_i\le 10^9)$;

输出描述

输出一个正整数代表答案

样例

输入

5
1 2 3 4 5

输出

5