1005. Cartesian Sensei

题目描述

来自夏莱的 Sensei hezlik 最近准备筹划一张基沃托斯全体合照。为了让每一位学生都能在照片中占据合适的位置，他费尽千辛万苦，对着学生之间错综复杂的关系苦思冥想了一整夜，终于敲定了所有人的站位顺序。

然而，第二天早上刚睡醒，他便意识到自己忽视了一个极其严重的问题——学生们的身高差距。根据专业统计，最矮的伊吹只有 128cm，而最高的月咏足足有 180cm。若是直接按照原定顺序拍摄，照片效果显然会大打折扣。

为了解决这一难题，hezlik 提出了一个天才般的设想：根据摄影中的基本原则“远小近大”，可以让较矮的学生站得更靠前，较高的学生站得更靠后。只要安排得足够巧妙，就能让大家在照片中看起来拥有相近的“身高”。

不过，单纯调整前后位置还不够。为了让整张合照在结构上更加协调，hezlik 决定采用一种特殊的“笛卡尔树”型排布：每一段站位中最矮的学生作为核心，其左右两侧再分别按照相同规则继续安排。这样一来，整张合照不仅高度协调，还隐约形成了一棵优雅的树形结构。

当然，在正式拍摄之前，hezlik 还需要大量样本数据来打磨自己的方案。于是，他希望你从给定的学生身高序列中，找出尽可能长的区间，使得这些区间对应的“笛卡尔树”结构与开头的区间完全相同。

---

对一个序列递归地定义它的笛卡尔树（Cartesian tree）：取序列中值最小的元素作为根，若最小值有多个则取最靠左的那个；该元素把序列分成左、右两段，分别递归构造为根的左子树与右子树（空序列对应空树）。记序列 P 的笛卡尔树为 CT(P)。这样得到的是一棵满足小根堆性质的有序二叉树，其中序遍历与原序列的顺序一致。

称两棵笛卡尔树等价，当且仅当它们形态完全相同：作为区分左、右孩子的有根二叉树是同构的（每个对应结点的左孩子、右孩子的存在性都一致）。

给定长度为 n 的整数序列 $a_1, a_2, …, a_n$。用 $a_{l\ldots r}$ 表示子段 $a_l, a_{l+1}, …, a_r$。

对每个 $i$（$1 ≤ i ≤ n$），求最大的整数 $j$ 满足

$$0 \le j < i \quad\text{且}\quad CT(a_{1\ldots j}) \text{ 与 } CT(a_{i-j+1\ldots i}) \text{ 等价}$$

即：在以位置 $i$ 结尾的所有后缀中，找出与序列前缀笛卡尔树等价的最长真前缀长度。$i=1$ 时假定 $j=0$。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来每组数据两行：第一行一个整数 $n$；第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

• $1\le T$
• $1 \le n \le 10^6$
• $1\le \sum n \le 2\times 10^6$
• $1 \le a_i \le 10^9$

输出格式

对每组数据输出一行 $n$ 个整数，第 $i$ 个表示下标 $i$ 对应的答案，相邻两数以单个空格分隔。

样例输入

1
5
2 1 3 1 2

样例输出

0 1 1 2 3

提示

• $i=1$：按照题目约定，答案为 $0$。

• $i=2$：取 $j=1$，比较 $[2]$ 与 $[1]$。单个元素构成的笛卡尔树均只有一个结点，因此答案为 $1$。

• $i=3$：

  当 $j=2$ 时，比较 $[2,1]$ 与 $[1,3]$。前者的根有左孩子，后者的根有右孩子，二者不等价。

  当 $j=1$ 时，两棵树均只有一个结点。

  因此答案为 $1$。

• $i=4$：

  当 $j=3$ 时，比较 $[2,1,3]$ 与 $[1,3,1]$，二者的笛卡尔树形态不同。

  当 $j=2$ 时，比较 $[2,1]$ 与 $[3,1]$。两者的最小值均位于第二个位置，因此笛卡尔树均为“根结点只有一个左孩子”的形态。

  因此答案为 $2$。

• $i=5$：

  当 $j=4$ 时，比较 $[2,1,3,1]$ 与 $[1,3,1,2]$，二者的笛卡尔树形态不同。

  当 $j=3$ 时，比较 $[2,1,3]$ 与 $[3,1,2]$。两者的最小值均位于中间，笛卡尔树均为根结点同时拥有左右孩子的形态。

  因此答案为 $3$。

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1005