A74561.博弈

Alice 和 Bob 在进行一场博弈游戏，现在桌上有 $n$ 盘饼干，第 $i$ 盘饼干有 $a_i$ 个，他们两轮流取走饼干，Alice 先手。

在每个玩家的回合时，玩家将按顺序进行以下两个步骤：

1. 选择一个非空的盘子，从中取走正数个饼干。
2. 对于这盘中剩下的饼干，保持不动或者把这些饼干全部合并到另一个非空的盘子。

最终无法操作的人将输掉这场游戏。

现在，有 $q$ 次询问，每次会询问一个区间 $[l,r]$ ，请回答区间 $[l,r]$ 中有多少个子段 Alice 可以获胜。

第一行输入一个正整数 $n$ $(1\leq n\leq 2\times 10^5)$ ，表示盘子的数量。

第二行输入 $n$ 个正整数 $a_i$ $(1\leq a_i\leq 10^6)$ ，表示第 $i$ 个盘子中饼干的数量。

第三行输入一个正整数 $q$ $(1\leq q\leq 2\times 10^5)$ ，表示询问次数。

接下来 $q$ 行，每行输入两个正整数 $l,r$ $(1\leq l \leq r\leq n)$ ，表示查询的区间范围。

输出共 $q$ 行，对于每个询问，输出一个正整数表示询问区间中 Alice 可以获胜的子段个数。