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 JAVA):

Solution:
/**
 * ******* Created on 14/11/19 4:45 PM*******
 */

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class F612Ed4 implements Runnable {

    private static final int MAX = 2005;
    private static final int MOD = (int) 1e9 + 7;
    private static final int Inf = (int) 1e9 + 10;
    int[]  a =new int[MAX];
    List<Integer> un;
    List<Integer> ind[] = new List[MAX];
    int[] lef = new int[MAX];
    int[] rig = new int[MAX];
    int[][][] dp = new int[MAX][2][MAX];
    int[][][] par = new int[MAX][2][MAX];
    int[][][] wth = new int[MAX][2][MAX];
    List<Pair> res;
    int n;
    class Pair{
        char c;
        int a;
        Pair(char c, int a){
            this.c =c;
            this.a =a;
        }
    }
    private void solve() throws IOException {
        n = reader.nextInt();
        int s = reader.nextInt();s--;
        un = new ArrayList<>();
        res = new ArrayList<>();
        List<Integer> temp =new ArrayList<>();
        for(int i=0;i<=n;i++)
            ind[i] = new ArrayList<>();
        for(int i=0;i<n;i++){
            a[i] = reader.nextInt();
            temp.add(a[i]);
        }
        Collections.sort(temp);
        un = temp.stream().distinct().collect(Collectors.toList());
        Collections.sort(un);
        for(int i=0;i<n;i++){
            a[i] =lowerBound(un, a[i]);
            ind[a[i]].add(i);
        }
        for(int i=0;i<n;i++){
            if(ind[a[i]].size() > 1){
                int my = lowerBound(ind[a[i]],i);
                my = (my-1 + ind[a[i]].size())% ind[a[i]].size();
                lef[i] = ind[a[i]].get(my);
                my = (my+2)% ind[a[i]].size();
                rig[i] = ind[a[i]].get(my);
            }
        }
        for(int i=0;i<MAX;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<MAX;k++)
                    dp[i][j][k] = Inf;


         for(int i=0;i< ind[0].size();i++){
             dp[0][0][ind[0].get(i)] = Best(s,ind[0].get(i));
             par[0][0][ind[0].get(i)] = s;
         }
         for(int i=0;i<un.size();i++){
             for(int z =0;z< ind[i].size();z++){
                 int j = ind[i].get(z);
                 if(ind[i].size()==1){
                     dp[i][1][j] = dp[i][0][j];
                     par[i][1][j] = j;
                 }else{
                     for(int c=0;c< ind[i].size();c++){
                         int k = ind[i].get(c);
                         if(k ==j)continue;
                         int cand = dp[i][0][j] +2*Rot(rig[k],j) + Rot(j,k);
                         if(cand < dp[i][1][k]){
                             dp[i][1][k] = cand ;
                             par[i][1][k]= j;
                             wth[i][1][k]=-1;
                         }
                         cand = dp[i][0][j] + 2*Rot(j,lef[k]) + Rot(k,j);
                         if(cand < dp[i][1][k]){
                             dp[i][1][k] = cand;
                             par[i][1][k]= j;
                             wth[i][1][k]= 1;
                         }
                     }
                 }
             }

             for(int z =0;z< ind[i].size();z++){
                 int j = ind[i].get(z);
                 for(int c =0;c< ind[i+1].size();c++){
                     int k = ind[i+1].get(c);
                     int cand = dp[i][1][j] + Best(j,k);
                     if(dp[i+1][0][k] > cand) {
                         dp[i+1][0][k]=cand;
                         par[i+1][0][k] = j;
                     }
                 }
             }


         }

         int best = Inf;
         int bj=-1;
         for(int i=0;i<n;i++)
         {
             if(dp[un.size()-1][1][i] < best) {
                 best =dp[un.size()-1][1][i];
                 bj =i;
             }
         }

         writer.println(best);
         Get(un.size()-1, 1 , bj);

         for(int i=0;i<res.size();i++)
             writer.println(res.get(i).c +""+res.get(i).a);
    }

    private void Get(int i, int f, int k) {
        if(i <0)return;
        if(f ==0){
            int j = par[i][f][k];
            Get(i-1,1,j);
            if(Best(j,k) == Rot(j,k) )
                res.add(new Pair('+',Rot(j,k)));
            else
                res.add(new Pair('-', Rot(k,j)));
        }
        else if(par[i][f][k] ==k )
            Get(i,0,k);
        else{
            int j = par[i][f][k];
            Get(i,0,j);
            int n = ind[i].size();
            int kind  =lowerBound(ind[i], k);
            List<Integer> tmp = new ArrayList<>();
            int jind=-1;
            if(wth[i][f][k] ==-1){
                for(int z=1;z<=n;z++)
                    tmp.add(ind[i].get( (kind+z)%n ));
                for(int z =0;z<tmp.size();z++)
                    if(tmp.get(z) == j){
                        jind =z; break;
                    }
                int lst =j;
                for(int z = jind-1; z>=0;z--) {
                    res.add(new Pair('-', Rot(tmp.get(z), lst)));
                    lst =tmp.get(z);
                }

                for(int z = jind+1 ; z< tmp.size();z++){
                    res.add(new Pair('+', Rot(lst, tmp.get(z))));
                    lst = tmp.get(z);
                }
            }else{
                for(int z =0;z<n;z++)
                    tmp.add(ind[i].get((kind+z)%n));
                for(int z=0; z< tmp.size();z++){
                    if(tmp.get(z)==j) {
                        jind = z;break;
                    }
                }

                int lst =j;
                for(int z = jind+1; z<tmp.size();z++){
                    res.add(new Pair('+', Rot(lst, tmp.get(z))));
                    lst =tmp.get(z);
                }
                for(int z = jind-1; z>=0;z--){
                    res.add(new Pair('-',Rot(tmp.get(z), lst)));
                    lst = tmp.get(z);
                }
            }
        }
    }

    private int Best(int a, int b ) {
        return Math.min(Rot(a,b), Rot(b,a));
    }

    private int Rot(int a, int b) {
        if(a<=b)
            return b-a;
        else
            return n + (b-a);
    }

    private int lowerBound(List<Integer> un, int val) {
        int l =0, r = un.size()-1;
        int ans = un.size();
        while(l <=r){
            int m = (l+r)>>1;
            if(un.get(m) < val)
                l =m+1;
            else{
                ans = m;
                r = m-1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new F612Ed4().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        default double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}