给定一个包含 n 个元素的循环数组。这些元素从某个元素开始按顺时针顺序编号,其值从 1 到 n。第 i 个单元格包含值 ai。机器人辛巴在 s 号牢房中。
机器人在每个时刻都位于 n 个单元格中的某些单元格中(一开始他位于 s 中)。一转,机器人可以写出当前单元格中写入的数字,或者以顺时针或逆时针方向移动到相邻的单元格。 Simba 写出单元格中的数字不需要花费任何时间,但移动到相邻单元格 Simba 需要花费一个单位的时间。
Simba 想要将每个单元格中的数字写入一次,因此数字将以非递减顺序写入。找出最少的时间单位来写出所有数字。
输入
第一行包含两个整数 n 和 s (1 ≤ s ≤ n ≤ 2000) — 圆形数组中的单元格数量和 Simba 的起始位置。
第二行包含 n 个整数 ai ( - 109 ≤ ai ≤ 109) — 第 i 个单元格中写入的数字。单元格的编号按从 1 到 n 的顺序给出。一些数字 ai 可以相等。
输出
在第一行中打印数字 t — 最小时间单位数。
接下来的 n 行中的每一行都应包含机器人移动的方向以及沿该方向移动的单元格数量。移动完成后,机器人会从它所在的单元格中写出数字。顺时针移动时应以+x 的形式打印单元格的方向和数量,逆时针移动时应以-x 的形式打印到x 个单元格(0 ≤ x ≤ n - 1)。
请注意,x 的绝对值之和应等于 t。
示例
输入 #1
9 1 0 1 2 2 2 1 0 1 1
输出 #1
12 +0 -3 -1 +2 +1 +2 +1 +1 +1
输入 #2
8 1 0 1 0 1 0 1 0 1
输出 #2
13 +0 +2 +2 +2 -1 +2 +2 +2
输入 #3
8 1 1 2 3 4 5 6 7 8
输出 #3
7 +0 +1 +1 +1 +1 +1 +1 +1
输入#4
8 1 0 0 0 0 0 0 0 0
输出#4
7 +0 +1 +1 +1 +1 +1 +1 +1