传统题 1000ms 256MiB

我什么都做得到

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

我什么都做得到

题目描述

小三月跟随列车组来到了匹诺康尼--梦的国度。(由于出题人在命题的时候还没进入2.02.0,所以他正好只好肆意妄想一下。)

匹诺康尼的梦境世界都是由0101构成的,比如说33就是111177就是1111113737就是100101100101等。当然,它们的前面都可以有任意多个00.

“既然在梦里,那我岂不是什么都做得到!”,小三月这么想着。于是她就梦到了这样的操作规则:对于两个数字,首先得出构成它们的0101串,然后她可以交换二者从后往前相同位置的数字。比如说,111111100101100101交换第22位就是(101,100111)(101,100111),交换第66位就是(100111,101).(100111,101).

现在你在小三月的梦境中看到了nn个数字,你可以通过小三月给出的规则不断改变这nn个数字,并希望给出最大的极差。

极差:一个列表的极差指的是它的最大值减去最小值。

数据格式

输入

第一行,一个正整数TT. 表示测试用例的组数。

每组测试用例两行。

第一行,一个正整数nn.

第二行,nn个正整数aia_i

输出

通过小三月的规则可以得出的最大极差。

样例

输入

4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36

输出

1
0
7
125

数据范围及约定

T104T \le 10^4

n105\sum n \le 10^5

ai109a_i \le 10^9

2024年南京师范大学迎新春赛

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2024-2-7 8:00
结束于
2024-2-9 12:00
持续时间
52 小时
主持人
参赛人数
117