配点 : 1000 点
問題文
N 有一个台阶场地。台阶场地上有 1, 2, …, N 的编号。每个 i (1≤i≤N)关于,台阶场地 i 的高度是 h_i 。
最初、足場 1 上有一只青蛙。青蛙会重复若干次以下动作,台阶 N 我正试图到达。 当在
- 足場 i 时,跳到平台 i+1 这个类型的变量里只能放入 i+2 。此时,将跳跃目的地的平台称为 j ,成本 |h_i - h_j| 。
青蛙在脚下 N 为止所支付的总成本最小的移动方法 1 的程序。
制約
- 2 ≤ N ≤ 100\,000
- 1 ≤ h_i ≤ 10\,000 (1 ≤ i ≤ N)
- 输入的值全部都是整数。
入力
输入将以以下形式从标准输入给出。
N h_1 h_2 \cdots h_N
出力
足場 P_1 → 足場 P_2 → ・・・ → 足場 P_K 如果是通过这个路径移动,请以以下格式输出。尤其要注意,P_1=1、P_K=N 必须如此。
K P_1 P_2 \cdots P_K
入力例 1
4 10 30 40 20
出力例 1
3 1 2 4
入力例 2
2 10 10
出力例 2
2 1 2
入力例 3
6 30 10 60 10 60 50
出力例 3
4 1 3 5 6