解题思路

• 比赛为单败淘汰，按当前顺序两两配对，胜者保持相对顺序进入下一轮。设队伍 1 的能力值为 s1。
• 第 r 轮（从 1 开始）结束后，区间 [1, 2^r] 的冠军一定是该区间内能力值最大的队伍（因为每一场都强者胜出且数值互不相同）。
• 因此，“队伍 1 能赢下前 r 轮” 等价于 s1 > max(s2, s3, …, s_{2^r})。
• 于是胜场数就是满足上述不等式的最大 r。
• 实现：一次线性扫描维护前缀最大值 m = max(s2..si)，当扫描到位置 i 使得 i+1 为 2 的幂（即 2,4,8,...）时检查 s1 > m。若为真则胜场加一并继续，否则立即停止。n=1 时无比赛，答案为 0。

复杂度分析

题目内容

给定一个长度为 $n=2^k$ 的整数数组 $s$ 表示 $n$ 支队伍的能力值，按初始顺序编号为 $1,2,...,n$ 。你位于第 $1$ 位(即队伍 $1$ )。

比赛采用单败淘汰制。每一轮中，按当前顺序相邻两队进行对决 $(1,2),(3,4),(5,6),...$，能力值较高者胜出并按原相对顺序进入下一轮。重复该流程，直到仅剩一支队伍为止。

定义每场对决都由能力值较高的队伍获胜；为保证胜负唯一，保证所有队伍的能力值两两不同。请计算你(队伍 $1$ )在整个淘汰赛中将获胜的总场次；若你在首轮即被淘汰，则胜场为 $0$ 。当 $n=1$ 时，你无需比赛，胜场为 $0$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^5)$ 表示数据组数。每组测试数据描述如下：

第一行输入一个整数 $n$ ，保证 $n(1≤n≤ 10^5)$ 是 $2$ 的整次幕；

第二行输入 $n$ 个两两不同的整数，表示数组 $s_1,s_2,...,s_n(0≤s_i≤ 10^5)$ 。

可保证所有测试中 $n$ 的总和不超过 $2× 10^5$ 。

输出描述

对于每组测试数据，输出一行，一个整数，表示你将获得的胜场数。

样例1

输入

2
8
7 3 5 2 6 1 4 0
4
5 6 1 2

输出

3
0

说明

第一组：首轮对决为

$(7,3)→7,(5,2)→5,(6,1)→6,(4,0)→4$ ，晋级序列为 $[7,5,6,4]$ ；第二轮为 $(7,5)→7,(6,4)→6$，晋级序列为 $[7,6]$ ；决赛为 $(7,6)→7$ 。你共胜 $3$ 场。

第二组：首轮即与 $6$ 对决且落败，胜场为 $0$ 。