题目描述

这一年最大的事件对于克罗地亚队来说以悲剧告终。CERC 有史以来最具影响力的理论家、热门页面 CERC Tips 的创始人，同时也是一位杰出的贝斯手，在他最近的一次表演中未能将他的团队带入决赛。

为了克服他的存在主义困扰，我们的主角正在通过玩几率游戏来消磨时间。他对以下游戏特别感兴趣：

给定一个正整数 M。我们的主角面前有一个数组 0, 1, 2, ..., $2^M$-1 的排列。

计算机选择给定排列中的一个非空连续子序列，然后将其点亮在东南欧某国的首都上空。

我们的知己，在摆脱旧时记忆带来的泪水后，必须选择排列中的两个不同元素并交换它们的位置。只有当替换后的点亮子序列的按位异或结果恰好为 $2^M$-1 时，我们的主角才会获胜。

我们的英雄想知道计算机可以点亮的连续子序列的数量，以便他能够获胜。

帮助我们的英雄克服他的身份危机，以便我们喜爱的页面能够再次全面活跃。

输入格式

输入的第一行包含整数 M (1 ≤ M ≤ 20)。

接下来的行包含 $2^M$ 个以空格分隔的数字，这些数字构成了数组 0, 1, 2, ..., $2^M$-1 的一个排列。

输出格式

你必须输出计算机可以点亮以使我们的英雄获胜的连续子序列的总数。

输入输出样例 #1

输入 #1

2
0 1 2 3

输出 #1

9

输入输出样例 #2

输入 #2

3
3 7 0 4 6 1 5 2

输出 #2

33

输入输出样例 #3

输入 #3

4
13 0 15 12 4 8 7 3
11 14 6 10 1 5 9 2

输出 #3

133

说明/提示

在占总分 50% 的测试用例中，1 ≤ M ≤ 14。

测试用例的说明：

在第一个测试用例中，如果计算机选择子序列 [1 2 3]，我们的英雄可以替换数字 0 和 3。在这种情况下，他实际上可以在每个选择的连续子序列中获胜，除了整个数组。

在第二个测试用例中，如果计算机选择整个数组 [3 7 0 4 6 1 5 2] 作为点亮的子序列，我们的英雄无论如何交换两个元素都无法改变子序列的异或结果（结果为 0）。

题面翻译由 ChatGPT-4o 提供。