#P3183. Stump Removal

Stump Removal

题目描述

FJ一直想着奶牛的放牧体验,发现必须从牧场上移除N(1 ≤ N ≤ 50,000)个难看的树桩。这些树桩整齐地排列成一条直线,编号为1..N,每个树桩的高度为Hᵢ(1 ≤ Hᵢ ≤ 10,000)。

FJ将使用传统的烈性炸药来摧毁树桩。这些炸药的特性是:只要相邻的树桩严格矮于当前被摧毁的树桩,就会被连锁摧毁。爆炸可以穿过最近的相邻树桩,继续作用于下一个相邻树桩,只要它比刚刚被摧毁的树桩更矮。然而,一旦爆炸波遇到不满足“严格更矮”条件的树桩,该方向的摧毁就会停止(另一侧的摧毁遵循相同规则)。

以一排九个树桩的高度为例:
1 2 5 4 3 3 6 6 2

如果FJ炸毁第三个树桩(高度为5),那么第二个树桩(高度2)会被摧毁,第一个树桩(高度1)也会被摧毁。同理,第四个树桩(高度4)和第五个树桩(高度3)会因依次更矮而被摧毁,剩下的树桩状态如下:
* * * * * 3 6 6 2

再用两次炸药(炸毁第七个和第八个树桩)即可摧毁剩余树桩。

请帮助FJ确定摧毁所有树桩所需的最少炸药数量,并输出引爆的树桩索引(按升序排列)。

输入格式

  • 第1行:单个整数N。
  • 第2到N+1行:第i+1行包含一个整数Hᵢ,表示第i个树桩的高度。

输出格式

  • 按升序输出每个需要引爆的树桩索引,每个索引占一行。

输入样例

9  
1  
2  
5  
4  
3  
3  
6  
6  
2  

输出样例

3  
7  
8  

题目来源

USACO 2006年1月青铜组竞赛