#P19007. 【CodeChef START263A】Telephone

【CodeChef START263A】Telephone

题目描述

NN 个人围成一圈,沿顺时针方向依次编号为 1,2,…,N1,2,\ldots,N。第 ii 个人手中的初始数字为 AiA_i。

每过一秒,所有人同时更换数字。每个人比较这一秒开始时左右两位邻居的数字,并把自己的数字改成其中较大的一个。也就是说,位置 ii 的新值是 max⁡(Ai−1,Ai+1)\max(A_{i-1},A_{i+1}),右边的两个值都取自本轮更新之前。编号按环处理,位置 11 和位置 NN 互为邻居。

求至少经过多少秒,所有人的数字才会相同。如果初始时已经相同,答案为 00。如果始终无法相同,输出 −1-1。

输入格式

第一行是整数 TT,表示测试组数。

每组数据占两行。第一行是人数 NN,第二行是 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N,按编号给出每个人的初始数字。

输出格式

每组数据输出一行,包含一个整数,表示所求的最少秒数或 −1-1。

数据范围

  • 1≤T≤1051 \le T \le 10^5。
  • 3≤N≤2⋅1053 \le N \le 2 \cdot 10^5。
  • 1≤Ai≤1091 \le A_i \le 10^9。
  • 所有测试组的 NN 之和不超过 2⋅1052 \cdot 10^5。

样例

4
6
3 8 2 8 6 1
5
4 2 7 3 5
8
6 9 4 1 7 3 9 2
7
5 9 2 6 9 1 4
-1
4
3
4

CodeChef 原题:Telephone