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 namespace std;
int N, S;
typedef struct {
  int num;
  int pos;
} input_t;
input_t carray[2000 + 1];
enum {
  PATH_TYPE_DIRECT,
  PATH_TYPE_CIRCULAR,
  PATH_TYPE_ANY,
};
typedef struct {
  int subend;
  int type;
} subpath_t;
typedef struct {
  int end;
  vector<subpath_t> subpathlist;
} path_t;
typedef struct _group_dist_table_entry {
  int distance;
  vector<path_t> pathlist;
} group_dist_table_entry;
group_dist_table_entry groupDistFrom[2000 + 1];
typedef struct {
  int dist;
  int prvGrEnd;
  int grStart;
} GrLinkDist;
GrLinkDist distSumTo[2000 + 1];
class group_info {
 public:
  int startInSorted;
  int endInSorted;
};
group_info GI[2000 + 1];
int grCnt;
void show_groupDistFrom(int g);
int cir_dist_in_group(int from, int to) {
  int t;
  if (from > to) {
    t = from;
    from = to;
    to = t;
  }
  return N + carray[from].pos - carray[to].pos;
}
int line_dist_in_group(int from, int to) {
  int t;
  if (from > to) {
    t = from;
    from = to;
    to = t;
  }
  return carray[to].pos - carray[from].pos;
}
int get_move(int from, int to, int type) {
  int pos0, pos1;
  int ld, cd;
  if (type == PATH_TYPE_DIRECT) {
    return carray[to].pos - carray[from].pos;
  } else if (type == PATH_TYPE_CIRCULAR) {
    if (carray[from].pos < carray[to].pos) {
      return (N + carray[from].pos - carray[to].pos) * (-1);
    }
    return (N + carray[to].pos - carray[from].pos);
  }
  pos0 = carray[from].pos;
  pos1 = carray[to].pos;
  if (pos0 < pos1) {
    cd = N + pos0 - pos1;
    ld = pos1 - pos0;
    if (ld <= cd)
      return ld;
    else
      return cd * (-1);
  }
  cd = N + pos1 - pos0;
  ld = pos0 - pos1;
  if (ld <= cd)
    return ld * (-1);
  else
    return cd;
}
void build_group_dist_table(int gId) {
  int s, e;
  int gStart = GI[gId].startInSorted;
  int gEnd = GI[gId].endInSorted;
  if (gStart == gEnd) {
    path_t path;
    e = s = gStart;
    path.end = e;
    groupDistFrom[s].pathlist.push_back(path);
    groupDistFrom[s].distance = 0;
    return;
  }
  int contRange = carray[gEnd].pos - carray[gStart].pos;
  for (s = gStart; s <= gEnd; s++) {
    int minDist = INT_MAX;
    int minEnd;
    vector<path_t> minPathlist;
    for (e = gStart; e <= gEnd; e++) {
      if (s == e) continue;
      path_t path1, path2;
      path1.end = e;
      path2.end = e;
      vector<subpath_t> &subpathlist1 = path1.subpathlist;
      vector<subpath_t> &subpathlist2 = path2.subpathlist;
      subpath_t subpath;
      int pairDist1 = 0;
      int pairDist2 = 0;
      int re, le;
      if (e < gEnd)
        re = e + 1;
      else
        re = gStart;
      if (e > gStart)
        le = e - 1;
      else
        le = gEnd;
      if (s < e) {
        if (re > e) {
          if (s != re) {
            pairDist1 += cir_dist_in_group(s, re);
            subpath.subend = re;
            subpath.type = PATH_TYPE_CIRCULAR;
            subpathlist1.push_back(subpath);
          }
          pairDist1 += cir_dist_in_group(re, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_CIRCULAR;
          subpathlist1.push_back(subpath);
        } else {
          if (s != re) {
            pairDist1 += line_dist_in_group(s, re);
            subpath.subend = re;
            subpath.type = PATH_TYPE_DIRECT;
            subpathlist1.push_back(subpath);
          }
          pairDist1 += line_dist_in_group(re, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_DIRECT;
          subpathlist1.push_back(subpath);
        }
        {
          if (s != le) {
            pairDist2 += line_dist_in_group(s, le);
            subpath.subend = le;
            subpath.type = PATH_TYPE_DIRECT;
            subpathlist2.push_back(subpath);
          }
          pairDist2 += cir_dist_in_group(le, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_CIRCULAR;
          subpathlist2.push_back(subpath);
        }
      } else {
        if (le < e) {
          if (s != le) {
            pairDist1 += cir_dist_in_group(s, le);
            subpath.subend = le;
            subpath.type = PATH_TYPE_CIRCULAR;
            subpathlist1.push_back(subpath);
          }
          pairDist1 += cir_dist_in_group(le, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_CIRCULAR;
          subpathlist1.push_back(subpath);
        } else {
          if (s != le) {
            pairDist1 += line_dist_in_group(s, le);
            subpath.subend = le;
            subpath.type = PATH_TYPE_DIRECT;
            subpathlist1.push_back(subpath);
          }
          pairDist1 += line_dist_in_group(le, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_DIRECT;
          subpathlist1.push_back(subpath);
        }
        {
          if (s != re) {
            pairDist2 += line_dist_in_group(s, re);
            subpath.subend = re;
            subpath.type = PATH_TYPE_DIRECT;
            subpathlist2.push_back(subpath);
          }
          pairDist2 += cir_dist_in_group(re, e);
          subpath.subend = e;
          subpath.type = PATH_TYPE_CIRCULAR;
          subpathlist2.push_back(subpath);
        }
      }
      if (pairDist1 <= minDist) {
        if (pairDist1 < minDist) {
          groupDistFrom[s].pathlist.clear();
        }
        groupDistFrom[s].pathlist.push_back(path1);
        groupDistFrom[s].distance = minDist = pairDist1;
      }
      if (pairDist2 <= minDist) {
        if (pairDist2 < minDist) {
          groupDistFrom[s].pathlist.clear();
        }
        groupDistFrom[s].pathlist.push_back(path2);
        groupDistFrom[s].distance = minDist = pairDist2;
      }
    }
  }
  show_groupDistFrom(gId);
}
void show_carray(const char *exp) {}
void show_groupDistFrom(int g) {}
int minPathEnd;
int minSum = INT_MAX;
void find_solution() {
  int g;
  for (g = 0; g < grCnt; g++) {
    build_group_dist_table(g);
  }
  carray[0].pos = S;
  distSumTo[0].dist = 0;
  int si, di, gi, ngi;
  for (si = 1; si <= N; si++) {
    distSumTo[si].dist = INT_MAX;
  }
  for (gi = 0; gi < grCnt; gi++) {
    ngi = gi + 1;
    for (si = GI[gi].startInSorted; si <= GI[gi].endInSorted; si++) {
      if (distSumTo[si].dist == INT_MAX) continue;
      for (di = GI[ngi].startInSorted; di <= GI[ngi].endInSorted; di++) {
        int nsum = distSumTo[si].dist + abs(get_move(si, di, PATH_TYPE_ANY)) +
                   groupDistFrom[di].distance;
        vector<path_t>::iterator it;
        for (it = groupDistFrom[di].pathlist.begin();
             it != groupDistFrom[di].pathlist.end(); it++) {
          if (nsum < distSumTo[(*it).end].dist) {
            distSumTo[(*it).end].dist = nsum;
            distSumTo[(*it).end].grStart = di;
            distSumTo[(*it).end].prvGrEnd = si;
            if (ngi == (grCnt - 1)) {
              if (minSum > nsum) {
                minSum = nsum;
                minPathEnd = (*it).end;
              }
            }
          }
        }
      }
    }
  }
}
bool cmp(input_t a, input_t b) {
  if (a.num < b.num) return true;
  if (a.num > b.num) return false;
  if (a.pos < b.pos) return true;
  if (a.pos > b.pos) return false;
  return false;
}
typedef struct {
  int grId;
  int grStart;
  int grEnd;
} GroupPath_T;
stack<GroupPath_T> pathStack;
int visitFlag[2000 + 1] = {0};
void print_move(int from, int to, int type, bool groupLocal, int grId) {
  if (!groupLocal) {
    int move = get_move(from, to, PATH_TYPE_ANY);
    if (move >= 0) printf("+");
    printf("%d\n", move);
    visitFlag[to] = 1;
    return;
  }
  if (from == to) {
    printf("+0\n");
    visitFlag[to] = 1;
    return;
  }
  int inc = 1;
  if (carray[from].pos < carray[to].pos && type == PATH_TYPE_CIRCULAR) {
    inc = -1;
  } else if (carray[from].pos > carray[to].pos && type == PATH_TYPE_DIRECT) {
    inc = -1;
  }
  int i = from, pi;
  for (pi = i; i != to;) {
    int type;
    do {
      type = PATH_TYPE_DIRECT;
      i += inc;
      if (i > GI[grId].endInSorted) {
        i = GI[grId].startInSorted;
        type = PATH_TYPE_CIRCULAR;
      } else if (i < GI[grId].startInSorted) {
        i = GI[grId].endInSorted;
        type = PATH_TYPE_CIRCULAR;
      }
    } while (visitFlag[i] == 1);
    int move = get_move(pi, i, type);
    if (move >= 0) printf("+");
    printf("%d\n", move);
    visitFlag[i] = 1;
    pi = i;
  }
}
void print_path() {
  int grStart, grEnd = minPathEnd;
  int grId = grCnt - 1;
  for (; grEnd > 0; grEnd = distSumTo[grEnd].prvGrEnd, grId--) {
    GroupPath_T grPath;
    grPath.grStart = distSumTo[grEnd].grStart;
    grPath.grEnd = grEnd;
    grPath.grId = grId;
    pathStack.push(grPath);
  }
  int prevGrEnd = 0;
  while (pathStack.size() > 0) {
    GroupPath_T grPath = pathStack.top();
    grStart = grPath.grStart;
    grEnd = grPath.grEnd;
    grId = grPath.grId;
    pathStack.pop();
    print_move(prevGrEnd, grStart, PATH_TYPE_DIRECT, false, -1);
    vector<path_t>::iterator it;
    bool pathFound = false;
    for (it = groupDistFrom[grStart].pathlist.begin();
         it != groupDistFrom[grStart].pathlist.end(); it++) {
      if ((*it).end == grEnd) {
        pathFound = true;
        break;
      }
    }
    if (!pathFound) {
      cout << "Error!: not found Group Path!" << endl;
      continue;
    }
    int from = grStart, to;
    vector<subpath_t>::iterator iit;
    for (iit = (*it).subpathlist.begin(); iit != (*it).subpathlist.end();
         iit++) {
      to = (*iit).subend;
      print_move(from, to, (*iit).type, true, grId);
      from = (*iit).subend;
    }
    prevGrEnd = grEnd;
  }
}
int main(int argc, char **argv) {
  int i;
  cin >> N >> S;
  for (i = 1; i <= N; i++) {
    input_t in;
    cin >> in.num;
    in.pos = i;
    carray[i] = in;
  }
  show_carray("ORG");
  sort(&carray[1], &carray[N + 1], cmp);
  show_carray("SORTED");
  grCnt = 0;
  carray[0].num = INT_MIN;
  GI[grCnt++].startInSorted = 0;
  int prevNum = carray[0].num;
  for (i = 1; i <= N; i++) {
    if (carray[i].num > prevNum) {
      GI[grCnt - 1].endInSorted = i - 1;
      GI[grCnt++].startInSorted = i;
      prevNum = carray[i].num;
    }
  }
  GI[grCnt - 1].endInSorted = i - 1;
  find_solution();
  printf("%d\n", minSum);
  print_path();
  return 0;
}