Ziota found a video game called "Monster Invaders".

Similar to every other shooting RPG game, "Monster Invaders" involves killing monsters and bosses with guns.

For the sake of simplicity, we only consider two different types of monsters and three different types of guns.

Namely, the two types of monsters are: 

  * a normal monster with 1 hp. 
  * a boss with 2 hp. 



And the three types of guns are: 

  * Pistol, deals 1 hp in damage to one monster, r_1 reloading time 
  * Laser gun, deals 1 hp in damage to all the monsters in the current level (including the boss), r_2 reloading time 
  * AWP, instantly kills any monster, r_3 reloading time 



The guns are initially not loaded, and the Ziota can only reload 1 gun at a time.

The levels of the game can be considered as an array a_1, a_2, …, a_n, in which the i-th stage has a_i normal monsters and 1 boss. Due to the nature of the game, Ziota cannot use the Pistol (the first type of gun) or AWP (the third type of gun) to shoot the boss before killing all of the a_i normal monsters.

If Ziota damages the boss but does not kill it immediately, he is forced to move out of the current level to an arbitrary adjacent level (adjacent levels of level i (1 < i < n) are levels i - 1 and i + 1, the only adjacent level of level 1 is level 2, the only adjacent level of level n is level n - 1). Ziota can also choose to move to an adjacent level at any time. Each move between adjacent levels are managed by portals with d teleportation time.

In order not to disrupt the space-time continuum within the game, it is strictly forbidden to reload or shoot monsters during teleportation. 

Ziota starts the game at level 1. The objective of the game is rather simple, to kill all the bosses in all the levels. He is curious about the minimum time to finish the game (assuming it takes no time to shoot the monsters with a loaded gun and Ziota has infinite ammo on all the three guns). Please help him find this value.

Input

The first line of the input contains five integers separated by single spaces: n (2 ≤ n ≤ 10^6) — the number of stages, r_1, r_2, r_3 (1 ≤ r_1 ≤ r_2 ≤ r_3 ≤ 10^9) — the reload time of the three guns respectively, d (1 ≤ d ≤ 10^9) — the time of moving between adjacent levels.

The second line of the input contains n integers separated by single spaces a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6, 1 ≤ i ≤ n).

Output

Print one integer, the minimum time to finish the game.

Examples

Input


4 1 3 4 3
3 2 5 1


Output


34

Input


4 2 4 4 1
4 5 1 2


Output


31

Note

In the first test case, the optimal strategy is:

  * Use the pistol to kill three normal monsters and AWP to kill the boss (Total time 1⋅3+4=7) 
  * Move to stage two (Total time 7+3=10) 
  * Use the pistol twice and AWP to kill the boss (Total time 10+1⋅2+4=16) 
  * Move to stage three (Total time 16+3=19) 
  * Use the laser gun and forced to move to either stage four or two, here we move to stage four (Total time 19+3+3=25) 
  * Use the pistol once, use AWP to kill the boss (Total time 25+1⋅1+4=30) 
  * Move back to stage three (Total time 30+3=33) 
  * Kill the boss at stage three with the pistol (Total time 33+1=34) 



Note that here, we do not finish at level n, but when all the bosses are killed.

import java.awt.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.List;

import static java.lang.Math.*;


public class ArchiveSolving implements Runnable {

    // SOLUTION AT THE TOP OF CODE!!!
    // HACK ME PLEASE IF YOU CAN!!!
    // PLEASE!!!
    // PLEASE!!!
    // PLEASE!!!

    @SuppressWarnings("unused")
    private final static Random rnd = new Random();
    private final static String fileName = "";

    private static long BASE = 1000 * 1000 * 1000 + 7, PHI = BASE - 1;
    private static long MODULO = BASE; //998244353;

    private void solve() {
        int tests = 1; //readInt();
        for (int test = 1; test <= tests; ++test) {
            solveTest(test);
        }
    }

    private void solveTest(int test) {
        int n = readInt();

        long pistol = readInt();
        long laser = readInt();
        long sniper = readInt();
        long distance = readInt();

        long[] a = readLongArray(n);

        long[] ns = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            ns[i + 1] = pistol * a[i] + sniper;
        }

        long[] ls = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            ls[i + 1] = min(laser, pistol * a[i] + pistol) + pistol;
        }

        long[] dp = new long[n + 1];
        dp[0] = -distance;

        dp[1] = ns[1] + distance + dp[0];

        for (int i = 2; i <= n; ++i) {
            long l1 = ns[i] + distance + dp[i - 1];
            long l2 = min(
                    ls[i - 1] + distance + min(ls[i], ns[i]) + distance + distance,
                    min(ls[i - 1], ns[i - 1]) + distance + ls[i] + distance + distance
            ) + distance + dp[i - 2];

            dp[i] = min(l1, l2);
        }

        long ans = dp[n];

        long[] suffLs = new long[n + 2];
        for (int i = n; i >= 0; --i) {
            suffLs[i] = suffLs[i + 1] + ls[i];
        }

        for (int end = 1; end < n; ++end) {
            long killNotN = suffLs[end] - ls[n];
            long pathToNAndBack = distance * 2 * (n - end);

            long loopN = min(
                    ns[n],
                    ls[n] + distance + distance
            );

            ans = min(ans, killNotN + pathToNAndBack + loopN + distance + dp[end - 1]);
        }

//        dp[n] = min(dp[n],
//                ls[n - 1] + distance + ns[n] + distance + (distance + dp[n - 2])
//        );

        out.println(ans);
    }


    /////////////////////////////////////////////////////////////////////

    /////////////////////////////////////////////////////////////////////

    private final static boolean MULTIPLE_TESTS = true;
    private final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    private final static int MAX_STACK_SIZE = 128;

    private final static boolean OPTIMIZE_READ_NUMBERS = false;

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private static long inverse(long x) {
        return binpow(x, MODULO - 2);
    }

    private static long binpow(long base, long power) {
        if (power == 0) return 1;
        if ((power & 1) == 0) {
            long half = binpow(base, power >> 1);
            return mult(half, half);
        } else {
            long prev = binpow(base, power - 1);
            return mult(prev, base);
        }
    }

    private static long add(long a, long b) {
        return (a + b) % MODULO;
    }

    @SuppressWarnings("unused")
    private static long subtract(long a, long b) {
        return add(a, MODULO - b % MODULO);
    }

    private static long mult(long a, long b) {
        return ((a % MODULO) * (b % MODULO)) % MODULO;
    }

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    boolean yesNo(boolean yes) {
//        out.println(yes ? "YES" : "NO");
        out.println(yes ? "yes" : "no");
        return yes;
    }

    /////////////////////////////////////////////////////////////////////

    public void run() {
        try {
            timeInit();
            Locale.setDefault(Locale.US);

            init();

            if (ONLINE_JUDGE) {
                solve();
            } else {
                do {
                    try {
                        timeInit();
                        solve();
                        time();

                        out.println();
                        out.flush();
                    } catch (NumberFormatException | EOFException e) {
                        break;
                    }
                } while (MULTIPLE_TESTS);
            }

            out.close();
            time();
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    /////////////////////////////////////////////////////////////////////

    private BufferedReader in;
    private OutputWriter out;
    private StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new ArchiveSolving(), "", MAX_STACK_SIZE * (1L << 20)).start();
    }

    /////////////////////////////////////////////////////////////////////

    private void init() throws FileNotFoundException {
        Locale.setDefault(Locale.US);

        if (ONLINE_JUDGE) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new OutputWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new OutputWriter(fileName + ".txt");
            }
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new OutputWriter("output.txt");
        }
    }

    ////////////////////////////////////////////////////////////////

    private long timeBegin;

    private void timeInit() {
        this.timeBegin = System.currentTimeMillis();
    }

    private void time() {
        long timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    @SuppressWarnings("unused")
    private void debug(Object... objects) {
        if (ONLINE_JUDGE) {
            for (Object o : objects) {
                System.err.println(o.toString());
            }
        }
    }

    /////////////////////////////////////////////////////////////////////

    private String delim = " ";

    private String readNullableLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeIOException(e);
        }
    }

    private String readLine() {
        String line = readNullableLine();
        if (null == line) throw new EOFException();
        return line;
    }

    private String readString() {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(readLine(), delim);
        }

        return tok.nextToken(delim);
    }

    /////////////////////////////////////////////////////////////////

    private final char NOT_A_SYMBOL = '\0';

    @SuppressWarnings("unused")
    private char readChar() {
        try {
            int intValue = in.read();

            if (intValue == -1) {
                return NOT_A_SYMBOL;
            }

            return (char) intValue;
        } catch (IOException e) {
            throw new RuntimeIOException(e);
        }
    }

    private char[] readCharArray() {
        return readLine().toCharArray();
    }

    @SuppressWarnings("unused")
    private char[][] readCharField(int rowsCount) {
        char[][] field = new char[rowsCount][];
        for (int row = 0; row < rowsCount; ++row) {
            field[row] = readCharArray();
        }

        return field;
    }

    /////////////////////////////////////////////////////////////////

    private long optimizedReadLong() {
        int sign = 1;
        long result = 0;
        boolean started = false;
        while (true) {
            try {
                int j = in.read();
                if (-1 == j){
                    if (started) return sign * result;
                    throw new NumberFormatException();
                }

                if (j == '-') {
                    if (started) throw new NumberFormatException();
                    sign = -sign;
                }

                if ('0' <= j && j <= '9') {
                    result = result * 10 + j - '0';
                    started = true;
                } else if (started) {
                    return sign * result;
                }
            } catch (IOException e) {
                throw new RuntimeIOException(e);
            }
        }
    }

    private int readInt() {

        if (!OPTIMIZE_READ_NUMBERS) {
            return Integer.parseInt(readString());
        } else {
            return (int) optimizedReadLong();
        }
    }

    private int[] readIntArray(int size) {
        int[] array = new int[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readInt();
        }

        return array;
    }

    @SuppressWarnings("unused")
    private int[] readSortedIntArray(int size) {
        Integer[] array = new Integer[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readInt();
        }
        Arrays.sort(array);

        int[] sortedArray = new int[size];
        for (int index = 0; index < size; ++index) {
            sortedArray[index] = array[index];
        }

        return sortedArray;
    }

    private int[] readIntArrayWithDecrease(int size) {
        int[] array = readIntArray(size);

        for (int i = 0; i < size; ++i) {
            array[i]--;
        }

        return array;
    }

    ///////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private int[][] readIntMatrix(int rowsCount, int columnsCount) {
        int[][] matrix = new int[rowsCount][];

        for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
            matrix[rowIndex] = readIntArray(columnsCount);
        }

        return matrix;
    }

    @SuppressWarnings("unused")
    private int[][] readIntMatrixWithDecrease(int rowsCount, int columnsCount) {
        int[][] matrix = new int[rowsCount][];

        for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
            matrix[rowIndex] = readIntArrayWithDecrease(columnsCount);
        }

        return matrix;
    }

    ///////////////////////////////////////////////////////////////////

    private long readLong() {
        if (!OPTIMIZE_READ_NUMBERS) {
            return Long.parseLong(readString());
        } else {
            return optimizedReadLong();
        }
    }

    @SuppressWarnings("unused")
    private long[] readLongArray(int size) {
        long[] array = new long[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readLong();
        }

        return array;
    }

    @SuppressWarnings("unused")
    private long[] readSortedLongArray(int size) {
        long[] array = readLongArray(size);

        Long[] objArray = new Long[size];
        for (int index = 0; index < size; ++index) {
            objArray[index] = array[index];
        }

        Arrays.sort(objArray);

        for (int index = 0; index < size; ++index) {
            array[index] = objArray[index];
        }

        return array;
    }

    ////////////////////////////////////////////////////////////////////

    private double readDouble() {
        return Double.parseDouble(readString());
    }

    @SuppressWarnings("unused")
    private double[] readDoubleArray(int size) {
        double[] array = new double[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readDouble();
        }

        return array;
    }

    ////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private BigInteger readBigInteger() {
        return new BigInteger(readString());
    }

    @SuppressWarnings("unused")
    private BigDecimal readBigDecimal() {
        return new BigDecimal(readString());
    }

    /////////////////////////////////////////////////////////////////////

    private Point readPoint() {
        int x = readInt();
        int y = readInt();
        return new Point(x, y);
    }

    @SuppressWarnings("unused")
    private Point[] readPointArray(int size) {
        Point[] array = new Point[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readPoint();
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    @Deprecated
    @SuppressWarnings("unused")
    private List<Integer>[] readGraph(int vertexNumber, int edgeNumber) {
        @SuppressWarnings("unchecked")
        List<Integer>[] graph = new List[vertexNumber];

        for (int index = 0; index < vertexNumber; ++index) {
            graph[index] = new ArrayList<>();
        }

        while (edgeNumber-- > 0) {
            int from = readInt() - 1;
            int to = readInt() - 1;

            graph[from].add(to);
            graph[to].add(from);
        }

        return graph;
    }

    public long getBruteAnswer(int n, int k, Edge[][] graph) {
        class FromToEdge {
            int from, to;
            int w;

            public FromToEdge(int from, int to, int w) {
                this.from = from;
                this.to = to;
                this.w = w;
            }
        }

        FromToEdge[] edges = new FromToEdge[n - 1];
        for (int v = 0, index = 0; v < n; ++v) {
            for (Edge e : graph[v]) if (v < e.to) edges[index++] = new FromToEdge(v, e.to, e.w);
        }

        long bestAnswer = 0;

        int[] degrees = new int[n];
        for (int mask = 0; mask < (1 << edges.length); ++mask){
            Arrays.fill(degrees, 0);

            long sum = 0;
            for (int bit = 0; bit < edges.length; ++bit) {
                if (checkBit(mask, bit)) {
                    sum += edges[bit].w;

                    degrees[edges[bit].from]++;
                    degrees[edges[bit].to]++;
                }
            }

            for (int v = 0; v < n; ++v) {
                if (degrees[v] > k) sum = -1;
            }

            bestAnswer = Math.max(bestAnswer, sum);
        }

        return bestAnswer;
    }

    private static class GraphBuilder {

        final int size;
        final List<Integer>[] edges;

        static GraphBuilder createInstance(int size) {
            @SuppressWarnings("unchecked")
            List<Integer>[] edges = new List[size];
            for (int v = 0; v < size; ++v) {
                edges[v] = new ArrayList<>();
            }

            return new GraphBuilder(edges);
        }

        private GraphBuilder(List<Integer>[] edges) {
            this.size = edges.length;
            this.edges = edges;
        }

        public void addEdge(int from, int to) {
            addDirectedEdge(from, to);
            addDirectedEdge(to, from);
        }

        public void addDirectedEdge(int from, int to) {
            edges[from].add(to);
        }

        public int[][] build() {
            int[][] graph = new int[size][];
            for (int v = 0; v < size; ++v) {
                List<Integer> vEdges = edges[v];
                graph[v] = castInt(vEdges);
            }

            return graph;
        }
    }

    @SuppressWarnings("unused")
    private final static int ZERO_INDEXATION = 0, ONE_INDEXATION = 1;

    @SuppressWarnings("unused")
    private int[][] readUnweightedGraph(int vertexNumber, int edgesNumber) {
        return readUnweightedGraph(vertexNumber, edgesNumber, ONE_INDEXATION, false);
    }

    private int[][] readUnweightedGraph(int vertexNumber, int edgesNumber,
                                        int indexation, boolean directed
    ) {
        GraphBuilder graphBuilder = GraphBuilder.createInstance(vertexNumber);
        for (int i = 0; i < edgesNumber; ++i) {
            int from = readInt() - indexation;
            int to = readInt() - indexation;

            if (directed) graphBuilder.addDirectedEdge(from, to);
            else graphBuilder.addEdge(from, to);
        }

        return graphBuilder.build();
    }

    static class Edge {
        int to;
        int w;

        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    @SuppressWarnings("unused")
    private Edge[][] readWeightedGraph(int vertexNumber, int edgesNumber) {
        return readWeightedGraph(vertexNumber, edgesNumber, ONE_INDEXATION, false);
    }

    private Edge[][] readWeightedGraph(int vertexNumber, int edgesNumber,
                                       int indexation, boolean directed) {
        @SuppressWarnings("unchecked")
        List<Edge>[] graph = new List[vertexNumber];
        for (int v = 0; v < vertexNumber; ++v) {
            graph[v] = new ArrayList<>();
        }

        while (edgesNumber-- > 0) {
            int from = readInt() - indexation;
            int to = readInt() - indexation;
            int w = readInt();

            graph[from].add(new Edge(to, w));
            if (!directed) graph[to].add(new Edge(from, w));
        }

        Edge[][] graphArrays = new Edge[vertexNumber][];
        for (int v = 0; v < vertexNumber; ++v) {
            graphArrays[v] = graph[v].toArray(new Edge[0]);
        }

        return graphArrays;
    }

    /////////////////////////////////////////////////////////////////////

    private static class IntIndexPair {

        @SuppressWarnings("unused")
        static Comparator<IntIndexPair> increaseComparator = new Comparator<ArchiveSolving.IntIndexPair>() {
            @Override
            public int compare(ArchiveSolving.IntIndexPair indexPair1, ArchiveSolving.IntIndexPair indexPair2) {
                int value1 = indexPair1.value;
                int value2 = indexPair2.value;

                if (value1 != value2)return value1 - value2;

                int index1 = indexPair1.index;
                int index2 = indexPair2.index;

                return index1 - index2;
            }
        };

        @SuppressWarnings("unused")
        static Comparator<IntIndexPair> decreaseComparator = new Comparator<ArchiveSolving.IntIndexPair>() {
            @Override
            public int compare(ArchiveSolving.IntIndexPair indexPair1, ArchiveSolving.IntIndexPair indexPair2) {
                int value1 = indexPair1.value;
                int value2 = indexPair2.value;

                if (value1 != value2)return -(value1 - value2);

                int index1 = indexPair1.index;
                int index2 = indexPair2.index;

                return index1 - index2;
            }
        };

        @SuppressWarnings("unused")
        static IntIndexPair[] from(int[] array) {
            IntIndexPair[] iip = new IntIndexPair[array.length];
            for (int i = 0; i < array.length; ++i) {
                iip[i] = new IntIndexPair(array[i], i);
            }

            return iip;
        }

        int value, index;

        IntIndexPair(int value, int index) {
            super();
            this.value = value;
            this.index = index;
        }

        @SuppressWarnings("unused")
        int getRealIndex() {
            return index + 1;
        }
    }

    @SuppressWarnings("unused")
    private IntIndexPair[] readIntIndexArray(int size) {
        IntIndexPair[] array = new IntIndexPair[size];

        for (int index = 0; index < size; ++index) {
            array[index] = new IntIndexPair(readInt(), index);
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    private static class OutputWriter extends PrintWriter {

        final int DEFAULT_PRECISION = 12;

        private int precision;
        private String format, formatWithSpace;

        {
            precision = DEFAULT_PRECISION;

            format = createFormat(precision);
            formatWithSpace = format + " ";
        }

        OutputWriter(OutputStream out) {
            super(out);
        }

        OutputWriter(String fileName) throws FileNotFoundException {
            super(fileName);
        }

        int getPrecision() {
            return precision;
        }

        void setPrecision(int precision) {
            precision = max(0, precision);
            this.precision = precision;

            format = createFormat(precision);
            formatWithSpace = format + " ";
        }

        String createFormat(int precision) {
            return "%." + precision + "f";
        }

        @Override
        public void print(double d) {
            printf(format, d);
        }

        @Override
        public void println(double d) {
            print(d);
            println();
        }

        void printWithSpace(double d) {
            printf(formatWithSpace, d);
        }

        void printAll(double... d) {
            for (int i = 0; i < d.length - 1; ++i) {
                printWithSpace(d[i]);
            }

            print(d[d.length - 1]);
        }

        @SuppressWarnings("unused")
        void printlnAll(double... d) {
            printAll(d);
            println();
        }

        void printAll(int... array) {
            for (int value : array) {
                print(value + " ");
            }
        }

        @SuppressWarnings("unused")
        void printlnAll(int... array) {
            printAll(array);
            println();
        }

        void printIndexes(int... indexes) {
            for (int index : indexes) {
                print((index + 1) + " ");
            }
        }

        @SuppressWarnings("unused")
        void printlnIndexes(int... indexes) {
            printIndexes(indexes);
            println();
        }

        void printAll(long... array) {
            for (long value : array) {
                print(value + " ");
            }
        }

        @SuppressWarnings("unused")
        void printlnAll(long... array) {
            printAll(array);
            println();
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class EOFException extends RuntimeException {

        EOFException() {
            super();
        }
    }

    private static class RuntimeIOException extends RuntimeException {

        /**
         *
         */
        private static final long serialVersionUID = -6463830523020118289L;

        RuntimeIOException(Throwable cause) {
            super(cause);
        }
    }

    /////////////////////////////////////////////////////////////////////
    //////////////// Some useful constants andTo functions ////////////////
    /////////////////////////////////////////////////////////////////////

    private static void swap(int[] array, int i, int j) {
        if (i != j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

    private static <T> void swap(T[] array, int i, int j) {
        if (i != j) {
            T tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

    private static final int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final int[][] steps8 = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
            {-1, -1}, {1, 1}, {1, -1}, {-1, 1}
    };

    @SuppressWarnings("unused")
    private static boolean checkCell(int row, int rowsCount, int column, int columnsCount) {
        return checkIndex(row, rowsCount) && checkIndex(column, columnsCount);
    }

    private static boolean checkIndex(int index, int lim) {
        return (0 <= index && index < lim);
    }

    /////////////////////////////////////////////////////////////////////

    private static int getBit(long mask, int bit) {
        return (int) ((mask >> bit) & 1);
    }

    @SuppressWarnings("unused")
    private static boolean checkBit(long mask, int bit) {
        return getBit(mask, bit) != 0;
    }

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private static long getSum(int[] array) {
        long sum = 0;
        for (int value : array) {
            sum += value;
        }

        return sum;
    }

    private static long getSum(long[] array) {
        long sum = 0;
        for (long value : array) {
            sum += value;
        }

        return sum;
    }

    @SuppressWarnings("unused")
    private static Point getMinMax(int[] array) {
        int min = array[0];
        int max = array[0];

        for (int index = 0, size = array.length; index < size; ++index, ++index) {
            int value = array[index];

            if (index == size - 1) {
                min = min(min, value);
                max = max(max, value);
            } else {
                int otherValue = array[index + 1];

                if (value <= otherValue) {
                    min = min(min, value);
                    max = max(max, otherValue);
                } else {
                    min = min(min, otherValue);
                    max = max(max, value);
                }
            }
        }

        return new Point(min, max);
    }

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private static boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; ++d) {
            if (x % d == 0) return false;
        }

        return true;
    }

    @SuppressWarnings("unused")
    private static int[] getPrimes(int n) {
        boolean[] used = new boolean[n];
        used[0] = used[1] = true;

        int size = 0;
        for (int i = 2; i < n; ++i) {
            if (!used[i]) {
                ++size;
                for (int j = 2 * i; j < n; j += i) {
                    used[j] = true;
                }
            }
        }

        int[] primes = new int[size];
        for (int i = 0, cur = 0; i < n; ++i) {
            if (!used[i]) {
                primes[cur++] = i;
            }
        }

        return primes;
    }

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    static int[] getDivisors(int value) {
        List<Integer> divisors = new ArrayList<>();
        for (int divisor = 1; divisor * divisor <= value; ++divisor) {
            if (value % divisor == 0) {
                divisors.add(divisor);
                if (divisor * divisor != value) {
                    divisors.add(value / divisor);
                }
            }
        }

        return castInt(divisors);
    }

    @SuppressWarnings("unused")
    static long[] getDivisors(long value) {
        List<Long> divisors = new ArrayList<>();
        for (long divisor = 1; divisor * divisor <= value; ++divisor) {
            if (value % divisor == 0) {
                divisors.add(divisor);
                if (divisor * divisor != value) {
                    divisors.add(value / divisor);
                }
            }
        }

        return castLong(divisors);
    }

    /////////////////////////////////////////////////////////////////////

    @SuppressWarnings("unused")
    private static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    private static long gcd(long a, long b) {
        return (a == 0 ? b : gcd(b % a, a));
    }

    /////////////////////////////////////////////////////////////////////

    private static int[] castInt(List<Integer> list) {
        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; ++i) {
            array[i] = list.get(i);
        }

        return array;
    }

    @SuppressWarnings("unused")
    private static long[] castLong(List<Long> list) {
        long[] array = new long[list.size()];
        for (int i = 0; i < array.length; ++i) {
            array[i] = list.get(i);
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    /**
     * Generates list with keys 0..<n
     *
     * @param n - exclusive limit of sequence
     */
    @SuppressWarnings("unused")
    private static List<Integer> order(int n) {
        List<Integer> sequence = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            sequence.add(i);
        }

        return sequence;
    }

    @SuppressWarnings("unused")
    private static List<Integer> shuffled(List<Integer> list) {
        Collections.shuffle(list, rnd);
        return list;
    }

    ////////////////////////////////////////////////////////////////////

    private static void swap(long[] array, int i, int j) {
        if (i != j) {
            long tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

    private static int partition(long[] array, int startInclusive, int endExclusive) {
        int pivotIndex = rnd.nextInt(endExclusive - startInclusive) + startInclusive;
        return partition(array, startInclusive, endExclusive, pivotIndex);
    }

    private static int partition(long[] array, int startInclusive, int endExclusive, int pivotIndex) {
        int endInclusive = endExclusive - 1;

        long pivotValue = array[pivotIndex];
        swap(array, pivotIndex, endInclusive);

        int storeIndex = startInclusive;
        for (int index = startInclusive; index < endInclusive; ++index) {
            if (array[index] < pivotValue) {
                swap(array, storeIndex, index);
                ++storeIndex;
            }
        }

        swap(array, storeIndex, endInclusive);

        return storeIndex;
    }

    @SuppressWarnings("unused")
    private static long nthElement(long[] array, int index, int size) {
        int left = 0, right = size;
        while (true) {
            int mid = partition(array, left, right);

            if (mid == index) return array[mid];

            if (index < mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
    }
}