Problem: You are given a circular array with n elements. The elements are numbered from some element with values from 1 to n in clockwise order. The i-th cell contains the value ai. The robot Simba is in cell s.

Each moment of time the robot is in some of the n cells (at the begin he is in s). In one turn the robot can write out the number written in current cell or move to the adjacent cell in clockwise or counterclockwise direction. To write out the number from the cell Simba doesn't spend any time, but to move to adjacent cell Simba spends one unit of time.

Simba wants to write the number from each cell one time, so the numbers will be written in a non decreasing order. Find the least number of time units to write out all numbers.

Input

The first line contains two integers n and s (1 ≤ s ≤ n ≤ 2000) — the number of cells in the circular array and the starting position of Simba.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109) — the number written in the i-th cell. The numbers are given for cells in order from 1 to n. Some of numbers ai can be equal.

Output

In the first line print the number t — the least number of time units.

Each of the next n lines should contain the direction of robot movement and the number of cells to move in that direction. After that movement the robot writes out the number from the cell in which it turns out. The direction and the number of cells should be printed in the form of +x in case of clockwise movement and -x in case of counterclockwise movement to x cells (0 ≤ x ≤ n - 1).

Note that the sum of absolute values of x should be equal to t.

Examples

Input

9 1
0 1 2 2 2 1 0 1 1


Output

12
+0
-3
-1
+2
+1
+2
+1
+1
+1


Input

8 1
0 1 0 1 0 1 0 1


Output

13
+0
+2
+2
+2
-1
+2
+2
+2


Input

8 1
1 2 3 4 5 6 7 8


Output

7
+0
+1
+1
+1
+1
+1
+1
+1


Input

8 1
0 0 0 0 0 0 0 0


Output

7
+0
+1
+1
+1
+1
+1
+1
+1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using std::vector;
using Pos = size_t;
using Position = vector<Pos>;
using Offset = int64_t;
using Lenght = int64_t;
using Way = std::list<Offset>;
using Color = int64_t;
std::tuple<vector<Position>, Pos, size_t> ReadInput(
    std::istream& in_stream = std::cin);
void WriteAnswer(const Way& steps, std::ostream& out_stream = std::cout);
Way Solve(size_t size, Pos pos, const vector<Position>& coloring);
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  vector<Position> arrangment;
  Pos start;
  size_t size;
  std::tie(arrangment, start, size) = ReadInput();
  auto result = Solve(size, start, arrangment);
  WriteAnswer(result);
  return 0;
}
class DynamicWay {
 private:
  const Pos start;
  const size_t size;
  const vector<Position>& coloring;
  vector<vector<Lenght>> skip_cache, throw_cache;
  static Lenght Distance(Pos fst, Pos snd, size_t size);
  static Lenght RawDistance(Pos fst, Pos snd, size_t size);
  static Offset Step(Pos fst, Pos snd, size_t size);
  Lenght SkipLevel(Pos pos, size_t level, Way* result = nullptr);
  Lenght ThrowLevel(size_t pos, size_t level, Way* result = nullptr);

 public:
  DynamicWay(size_t size, Pos start, const vector<Position>& coloring);
  Lenght ShortestWay(size_t level, Pos pos, Way* result = nullptr);
};
Way Solve(size_t size, Pos start, const vector<Position>& coloring) {
  DynamicWay solve(size, start, coloring);
  Lenght lenght =
      solve.ShortestWay(coloring.size() - 1, coloring.back().front());
  Pos finish = coloring.back().front();
  for (auto maybe : coloring.back()) {
    Lenght potential = solve.ShortestWay(coloring.size() - 1, maybe);
    if (potential < lenght) {
      lenght = potential;
      finish = maybe;
    }
  }
  Way result;
  solve.ShortestWay(coloring.size() - 1, finish, &result);
  return result;
}
DynamicWay::DynamicWay(size_t size, Pos start, const vector<Position>& coloring)
    : start(start), size(size), coloring(coloring) {
  for (auto level : coloring) {
    skip_cache.push_back(vector<Lenght>(size, Lenght(0)));
    throw_cache.push_back(vector<Lenght>(level.size(), Lenght(0)));
  }
}
template <class Integral, class Functional, class Check>
Integral BinSearch(Integral left, Integral right, Functional func, Check check);
Lenght DynamicWay::ShortestWay(size_t level, Pos pos, Way* result) {
  size_t position = BinSearch(
      size_t(0), coloring.back().size(),
      [&](size_t idx) { return coloring.back()[idx] <= pos; },
      [](size_t l, size_t r) { return r - l <= 1; });
  return ThrowLevel(position, level, result);
}
Lenght DynamicWay::Distance(Pos fst, Pos snd, size_t size) {
  return std::abs(Step(fst, snd, size));
}
Lenght DynamicWay::RawDistance(Pos fst, Pos snd, size_t size) {
  Offset step = (static_cast<Offset>(fst) - static_cast<Offset>(snd) +
                 static_cast<Offset>(size)) %
                static_cast<Offset>(size);
  return static_cast<Lenght>(step);
}
Offset DynamicWay::Step(Pos lhs, Pos rhs, size_t size) {
  Offset fst = static_cast<Offset>(rhs) - static_cast<Offset>(lhs);
  if (fst < 0) {
    fst += static_cast<Offset>(size);
  }
  Offset snd = fst - static_cast<Offset>(size);
  if (std::abs(fst) <= std::abs(snd)) {
    return fst;
  } else {
    return snd;
  }
}
Lenght DynamicWay::SkipLevel(Pos pos, size_t level, Way* way) {
  if (skip_cache[level][pos] != 0 && way == nullptr) {
    return skip_cache[level][pos];
  }
  if (level == 0) {
    if (way != nullptr) {
      way->push_back(Step(start, pos, size));
    }
    return Distance(start, pos, size);
  }
  size_t best_pos = 0;
  Lenght& best_lenght = skip_cache[level][pos];
  best_lenght = ThrowLevel(best_pos, level - 1) +
                Distance(pos, coloring[level - 1][0], size);
  for (size_t pos_ = 1; pos_ < coloring[level - 1].size(); ++pos_) {
    Lenght possible = ThrowLevel(pos_, level - 1) +
                      Distance(pos, coloring[level - 1][pos_], size);
    if (possible < best_lenght) {
      best_lenght = possible;
      best_pos = pos_;
    }
  }
  if (way != nullptr) {
    ThrowLevel(best_pos, level - 1, way);
    way->push_back(Step(coloring[level - 1][best_pos], pos, size));
  }
  return best_lenght;
}
Lenght DynamicWay::ThrowLevel(size_t pos, size_t level, Way* result) {
  if (throw_cache[level][pos] != 0 && result == nullptr) {
    return throw_cache[level][pos];
  }
  Lenght less, more;
  Pos prev, next;
  if (pos > 0) {
    prev = coloring[level][pos - 1];
  } else {
    prev = coloring[level].back();
  }
  if (pos + 1 < coloring[level].size()) {
    next = coloring[level][pos + 1];
  } else {
    next = coloring[level].front();
  }
  less = RawDistance(prev, coloring[level][pos], size);
  more = RawDistance(coloring[level][pos], next, size);
  Lenght& answer = throw_cache[level][pos];
  less += SkipLevel(prev, level);
  more += SkipLevel(next, level);
  answer = std::min(less, more);
  if (result != nullptr) {
    bool dir;
    if (less < more) {
      SkipLevel(prev, level, result);
      dir = 1;
    } else {
      SkipLevel(next, level, result);
      dir = 0;
    }
    size_t range = coloring[level].size();
    size_t next_pos = pos, after_next;
    auto step = [range, dir](size_t& position) {
      if (!dir) {
        position = (position + 1) % range;
      } else {
        position = (position - 1 + range) % range;
      }
    };
    step(next_pos);
    after_next = next_pos;
    step(after_next);
    for (size_t lhs = next_pos, rhs = after_next; lhs != pos;
         step(lhs), step(rhs)) {
      result->push_back(Step(coloring[level][lhs], coloring[level][rhs], size));
    }
  }
  return answer;
}
template <class Integral, class Functional, class Check>
Integral BinSearch(Integral left, Integral right, Functional func,
                   Check check) {
  bool dir = func(left);
  while (!check(left, right)) {
    Integral mid = (left + right) / 2;
    if (func(mid) == dir) {
      left = mid;
    } else {
      right = mid;
    }
  }
  return left;
}
void WriteAnswer(const Way& steps, std::ostream& out_stream) {
  Lenght sum_offset = 0;
  std::for_each(steps.begin(), steps.end(), [&sum_offset](Offset offset) {
    sum_offset += std::abs(offset);
  });
  out_stream << sum_offset << '\n';
  for (auto step : steps) {
    out_stream << ((step >= 0) ? '+' : '-') << std::abs(step) << '\n';
  }
}
std::tuple<vector<Position>, Pos, size_t> ReadInput(std::istream& in_stream) {
  size_t size;
  Pos start;
  in_stream >> size >> start;
  --start;
  vector<Color> pure_coloring(size);
  for (auto& color : pure_coloring) {
    in_stream >> color;
  }
  vector<std::pair<Color, Pos>> some_magic;
  for (Pos i = 0; i < size; ++i) {
    some_magic.push_back({pure_coloring[i], i});
  }
  std::sort(some_magic.begin(), some_magic.end());
  vector<Position> levels;
  for (auto cell : some_magic) {
    if (levels.empty() || cell.first != pure_coloring[levels.back().back()]) {
      levels.push_back({cell.second});
    } else {
      levels.back().push_back(cell.second);
    }
  }
  return {levels, start, size};
}