← 返回题目列表

Codeforces · 319/B

B. 排队的精神病人

中文机器翻译题面 查看原题

有 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]。所以,有两个步骤。