← 返回题目列表

AtCoder · tessoku_book_cp

B17. 青蛙 1 恢复

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

配点 : 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