CF1696D Permutation Graph

给出一个 $1$ 到 $n$ 的排列 $ [a_1,a_2,\dots,a_n] $ 。对于 $1\le i < j\le n$ ，记 $ \operatorname{mn}(i,j) $ 为 $\min\limits_{k=i}^j a_k$ ，记 $ \operatorname{mx}(i,j) $ 为 $ \max\limits_{k=i}^j a_k $ 。 有一张 $n$ 个点的无向图，点的编号为 $1$ 到 $n$ 。对于每一对整数 $ 1\le i

每个数据点包含多组数据。第一行一个整数 $t$ ( $ 1 \le t \le 5\cdot 10^4 $ ) 表示测试组数 对于每组数据，第一行一个整数 $n$ ( $ 1\le n\le 2.5\cdot 10^5 $ ) 。 第二行包含 $n$ 个整数 $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_n $ ( $ 1\le a_i\le n $ ) 。保证 $a$ 是 $ 1 $ , $ 2 $ , $ \dots $ , $ n $ 的一个排列。 保证所有数据的 $n$ 之和不超过 $ 5\cdot 10^5 $

对于每组数据，输出一个整数表示从 $1$ 到 $n$ 的最短路长度

The following are illustrations of constructed graphs in example test cases. the constructed graph in test case 1 the constructed graph in test case 2 the constructed graph in test case 3 the constructed graph in test case 4 the constructed graph in test case 5