You are given an array of n integer numbers. Let sum(l, r) be the sum of all numbers on positions from l to r non-inclusive (l-th element is counted, r-th element is not counted). For indices l and r holds 0 ≤ l ≤ r ≤ n. Indices in array are numbered from 0. 

For example, if a = [ - 5, 3, 9, 4], then sum(0, 1) = - 5, sum(0, 2) = - 2, sum(1, 4) = 16 and sum(i, i) = 0 for each i from 0 to 4.

Choose the indices of three delimiters delim0, delim1, delim2 (0 ≤ delim0 ≤ delim1 ≤ delim2 ≤ n) and divide the array in such a way that the value of res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) is maximal. 

Note that some of the expressions sum(l, r) can correspond to empty segments (if l = r for some segment).

Input

The first line contains one integer number n (1 ≤ n ≤ 5000).

The second line contains n numbers a0, a1, ..., an - 1 ( - 109 ≤ ai ≤ 109).

Output

Choose three indices so that the value of res is maximal. If there are multiple answers, print any of them.

Examples

Input

3
-1 2 3


Output

0 1 3


Input

4
0 0 -1 0


Output

0 0 0


Input

1
10000


Output

1 1 1
import java.util.*;
import java.io.*;
import java.math.BigInteger;

/**
 *
 * @author usquare
 */

public class ProblemB
{

    static long mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    static void solve()
    {

        in = new InputReader(System.in);
        out = new PrintWriter(System.out);  
        
        int n = in.nextInt();
        long[] sum = new long[n + 1];
        
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + in.nextInt();
        
        long ans = Long.MIN_VALUE;
        int a = 0;
        int b = 0;
        int c = 0;
        
        for(int i = 0; i <= n; i++){
            int min = i;
            for(int j = i; j <= n; j++){
                if(sum[j] < sum[min])
                    min = j;
                long cur = 2 * sum[i] - 2 * sum[min] + 2 * sum[j] - sum[n];
                if(cur > ans){
                    ans = cur;
                    a = i;
                    b = min;
                    c = j;
                }
            }
        }
        
        out.println(a + " " + b + " " + c);
        out.close();

    }
    
    
    public static void main(String[] args)
    {

        new Thread(null,new Runnable()
        {
            @Override
            public void run()
            {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
    }

    static class Pair implements Comparable<Pair>
    {

        int i;
        int x, y;
        
	Pair (int x,int y,int i)
        {
		this.x = x;
		this.y = y;
                this.i = i;
	}
        
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
	public int compareTo(Pair o)
        {
            return Long.compare(this.i,o.i);
	}

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y + " "+i;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 


    static class Merge
    {

        public static void sort(int inputArr[])
        {
            int length = inputArr.length;
            doMergeSort(inputArr,0, length - 1);
        }

        private static void doMergeSort(int[] arr,int lowerIndex, int higherIndex)
        {        
            if (lowerIndex < higherIndex)
            {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                doMergeSort(arr,lowerIndex, middle);
                doMergeSort(arr,middle + 1, higherIndex);
                mergeParts(arr,lowerIndex, middle, higherIndex);
            }
        }

        private static void mergeParts(int[]array,int lowerIndex, int middle, int higherIndex)
        {
            int[] temp=new int[higherIndex-lowerIndex+1];
            for (int i = lowerIndex; i <= higherIndex; i++)
            {
                temp[i-lowerIndex] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex)
            {
                if (temp[i-lowerIndex] < temp[j-lowerIndex])
                {
                    array[k] = temp[i-lowerIndex];
                    i++;
                } else
                {
                    array[k] = temp[j-lowerIndex];
                    j++;
                }
                k++;
            }
            while (i <= middle)
            {
                array[k] = temp[i-lowerIndex];
                k++;
                i++;
            }
            while(j<=higherIndex)
            {
                array[k]=temp[j-lowerIndex];
                k++;
                j++;
            }
        }

    }

    static long add(long a,long b)
    {
        long x = a + b;
        if(x >= mod) x -= mod;
        return x;
    }

    static long sub(long a,long b)
    {
        long x= a - b ;
        if(x < 0) x += mod;
        return x;
    }

    static long mul(long a,long b)
    {
        a %= mod;
        b %= mod;
        long x = a*b;
        return x%mod;
    }


    static boolean isPal(String s)
    {
        for(int i=0, j=s.length()-1;i<=j;i++,j--)
        {
                if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    static String rev(String s)
    {
                StringBuilder sb=new StringBuilder(s);
                sb.reverse();
                return sb.toString();
    }

    static long gcd(long x,long y)
    {
        if(y==0)
                return x;
        else
                return gcd(y,x%y);
    }

    static int gcd(int x,int y)
    {
        if(y==0)
                return x;
        else 
                return gcd(y,x%y);
    }

    static long gcdExtended(long a,long b,long[] x)
    {

        if(a==0)
        {
            x[0]=0;
            x[1]=1;
            return b;
        }
        long[] y=new long[2];
        long gcd=gcdExtended(b%a, a, y);

        x[0]=y[1]-(b/a)*y[0];
        x[1]=y[0];

        return gcd;
    }


    static long mulmod(long  a,long b,long m)
    {
        if (m <= 1000000009) return a * b % m;

        long res = 0;
        while (a > 0)
        {
            if ((a&1)!=0)
            {
                res += b;
                if (res >= m) res -= m;
            }
            a >>= 1;
            b <<= 1;
            if (b >= m) b -= m;
        }
        return res;
    }

    static int abs(int a,int b)
    {
        return (int)Math.abs(a-b);
    }

    public static long abs(long a,long b)
    {
        return (long)Math.abs(a-b);
    }

    static int max(int a,int b)
    {
        if(a>b)
                return a;
        else
                return b;
    }

    static int min(int a,int b)
    {
        if(a>b)
                return b;
        else 
                return a;
    }

    static long max(long a,long b)
    {
        if(a>b)
                return a;
        else
                return b;
    }

    static long min(long a,long b)
    {
        if(a>b)
                return b;
        else 
                return a;
    }

    static long pow(long n,long p,long m)
    {
         long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;
            if(result>=m)
            result%=m;
            p >>=1;
            n*=n;
            if(n>=m)
            n%=m;
        }
        return result;
    }

    static long pow(long n,long p)
    {
        long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;	    
            p >>=1;
            n*=n;	    
        }
        return result;
    }

    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;

        public InputReader(InputStream st) {
                this.stream = st;
        }

        public int read() {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars) {
                        curChar = 0;
                        try {
                                snumChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                int res = 0;
                do {
                        res *= 10;
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                long res = 0;
                do {
                        res *= 10;
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextInt();
                }
                return a;
        }

        public String readString() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = read();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = read();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
        }

    }
}    
