有 n 个精神病患者排成一排。每个 Psycho 都被分配了一个从 1 到 n 的唯一整数。在每一步中,每个 id 大于其右侧精神病患者(如果存在)的精神病患者都会杀死队列中的右邻居。请注意,精神病患者可能会在同一步骤杀人和被杀。
你会得到队列中精神病患者的初始排列。计算到达该时刻需要多少步,使得在那一刻之后没有人杀死他的邻居。查看注释可以更准确地理解该语句。
输入
输入的第一行包含整数n,表示psychos的数量,(1 ≤ n ≤ 105)。在第二行中,将有一个由 n 个空格分隔的不同整数组成的列表,每个整数的范围为 1 到 n(包括 1 到 n)——从左到右该行中的精神病患者的 id。
输出
打印步骤数,以便之后的行保持不变。
示例
输入 #1
10 10 9 7 8 6 5 3 4 2 1
输出 #1
2
输入 #2
6 1 2 3 4 5 6
输出 #2
0
注意
在 Psychos 的第一个样本行中,变换如下:[10 9 7 8 6 5 3 4 2 1] → [10 8 4] → [10]。所以,有两个步骤。