1 10
1
 10 1
-1 1 1 1 1 1 1 1 1 1
 78 8
-230 -757 673 -284 381 -324 -96 975 249 971 -355 186 -526 804 147 -553 655 263 -247 775 108 -246 -107 25 -786 -372 -24 -619 265 -192 269 392 210 449 335 -207 371 562 307 141 668 78 13 251 623 -238 60 543 618 201 73 -35 -663 620 485 444 330 362 -33 484 685 257 542 375 -952 48 -604 -288 -19 -718 -798 946 -533 -666 -686 -278 368 -294
 82 8
-483 465 435 -789 80 -412 672 512 -755 981 784 -281 -634 -270 806 887 -495 -46 -244 609 42 -821 100 -40 -299 -6 560 941 523 758 -730 -930 91 -138 -299 0 533 -208 -416 869 967 -871 573 165 -279 298 934 -236 70 800 550 433 139 147 139 -212 137 -933 -863 876 -622 193 -121 -944 983 -592 -40 -712 891 985 16 580 -845 -903 -986 952 -95 -613 -2 -45 -86 -206
 6 9
-669 45 -220 544 106 680
 116 10
477 -765 -756 376 -48 -75 768 -658 263 -207 362 -535 96 -960 630 -686 609 -830 889 57 -239 346 -298 -18 -107 853 -607 -443 -517 371 657 105 479 498 -47 432 503 -917 -656 610 -466 216 -747 -587 -163 -174 493 -882 853 -582 -774 -477 -386 610 -58 557 968 196 69 610 -38 366 -79 574 170 317 332 189 158 -194 136 -151 500 309 624 316 543 472 132 -15 -78 166 360 -71 12 247 678 263 573 -198 1 101 155 -65 597 -93 60 3 -496 985 -586 -761 -532 506 578 -13 569 845 -341 870 -900 891 724 408 229 -210
 32 9
-650 -208 506 812 -540 -275 -272 -236 -96 197 425 475 81 570 281 633 449 396 401 -362 -379 667 717 875 658 114 294 100 286 112 -928 -373
 38 1
173 587 -788 163 83 -768 461 -527 350 3 -898 634 -217 -528 317 -238 545 93 -964 283 -798 -596 77 222 -370 -209 61 846 -831 -419 -366 -509 -356 -649 916 -391 981 -596
 9 9
-767 148 -323 -818 41 -228 615 885 -260
 24 5
-751 889 721 -900 903 -900 -693 895 828 314 836 -493 549 -74 264 662 229 517 -223 367 141 -99 -390 283
 18 1
166 788 276 -103 -491 195 -960 389 376 369 630 285 3 575 315 -987 820 466
 36 5
-286 762 -5 -230 -483 -140 -143 -82 -127 449 435 85 -262 567 454 -163 942 -679 -609 854 -533 717 -101 92 -767 795 -804 -953 -754 -251 -100 884 809 -358 469 -112
 11 7
877 -188 10 -175 217 -254 841 380 552 -607 228
 47 10
-175 246 -903 681 748 -338 333 0 666 245 370 402 -38 682 144 658 -10 313 295 351 -95 149 111 -210 645 -173 -276 690 593 697 259 698 421 584 -229 445 -215 -203 49 642 386 649 469 4 340 484 279
 1 10
-1
 1 1
1
 29 6
-21 486 -630 -433 -123 -387 618 110 -203 55 -123 524 -168 662 432 378 -155 -136 -162 811 457 -157 -215 861 -565 -506 557 348 -7
 1 1
-1
 94 2
432 255 304 757 -438 52 461 55 837 -564 304 713 -968 -539 -593 835 -824 -532 38 -880 -772 480 -755 -387 -830 286 -38 -202 -273 423 272 471 -224 306 490 532 -210 -245 -20 680 -236 404 -5 -188 387 582 -30 -800 276 -811 240 -4 214 -708 200 -785 -466 61 16 -742 647 -371 -851 -295 -552 480 38 924 403 704 -705 -972 677 569 450 446 816 396 -179 281 -564 -27 -272 -640 809 29 28 -209 -925 997 -268 133 265 161
 35 5
151 -160 -292 -31 -131 174 359 42 438 413 164 91 118 393 76 435 371 -76 145 605 292 578 623 405 664 330 455 329 66 168 179 -76 996 163 531
 110 4
-813 -73 334 667 602 -155 432 -133 689 397 461 499 630 40 69 299 697 449 -130 210 -146 415 292 123 12 -105 444 338 509 497 142 688 603 107 -108 160 211 -215 219 -144 637 -173 615 -210 521 545 377 -6 -187 354 647 309 139 309 155 -242 546 -231 -267 405 411 -271 -149 264 -169 -447 -749 -218 273 -798 -135 839 54 -764 279 -578 -641 -152 -881 241 174 31 525 621 -855 656 482 -197 -402 995 785 338 -733 293 606 294 -645 262 909 325 -246 -952 408 646 2 -567 -484 661 -390 -488

1
 9
 17941
 18704
 1375
 24624
 9049
 2743
 1689
 8398
 5016
 8222
 3105
 14728
 -1
 1
 6299
 -1
 7839
 9754
 20286

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ListIterator;
import java.util.AbstractList;
import java.util.InputMismatchException;
import java.util.Deque;
import java.util.NoSuchElementException;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.Collection;
import java.io.IOException;
import java.util.List;
import java.util.Comparator;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cunbidun
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CSerejaAndSwaps solver = new CSerejaAndSwaps();
        solver.solve(1, in, out);
        out.close();
    }

    static class CSerejaAndSwaps {
        private InputReader in;
        private PrintWriter out;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
            int n = in.nextInt();
            int m = in.nextInt();
            int[] a = in.nextIntArray(n, 1);
            int[] b = new int[n + 1];
            if (n >= 0) System.arraycopy(a, 1, b, 1, n);
            MergeSort.sort(b, 1, n, Comparator.reverseOrder());
            int defAns = b[1];
            for (int i = 2; i <= m; i++) {
                if (b[i] < 0) break;
                defAns += b[i];
            }
            SBTree<Integer>[] setB = new SBTree[n + 1];
            SBTree<Integer>[] setA = new SBTree[n + 1];
            for (int i = 1; i <= n; i++) {
                setA[i] = new SBTree<>(true);
                setB[i] = new SBTree<>(true);
            }
            for (int i = 1; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    setA[i].add(a[j]);
                }
                for (int j = i - 1; j >= 1; j--) {
                    setB[i].add(a[j]);
                }
            }
            int ans = defAns;
            for (int i = 1; i <= n; i++)
                for (int j = i + m - 1; j <= n; j++) {
                    int res = 0;
                    TreeList<Integer> listIn = new TreeList<>();
                    TreeList<Integer> listOut = new TreeList<>();

                    for (int k = i; k <= j; k++) listIn.add(a[k]);
                    Collections.sort(listIn);
                    for (int k = 0; k < listIn.size(); k++)
                        if (k < m) listOut.add(listIn.get(k));
                        else
                            res += listIn.get(k);
                    for (int k = 1; k <= m; k++) {
                        if (k > setA[j].size()) break;
                        listOut.add(setA[j].getKth(setA[j].size() - k + 1));
                    }

                    for (int k = 1; k <= m; k++) {
                        if (k > setB[i].size()) break;
                        listOut.add(setB[i].getKth(setB[i].size() - k + 1));
                    }
                    listOut.sort(Collections.reverseOrder());
                    for (int k = 0; k <= MaxMin.Min(listOut.size() - 1, m - 1); k++) {
                        if (res + listOut.get(k) < res) break;
                        res += listOut.get(k);
                    }
                    ans = MaxMin.Max(ans, res);
                }
            out.println(ans);
        }

    }

    static class SBTree<T extends Comparable<T>> {
        private Node<T> root;
        private boolean isMultiSet;

        public SBTree(boolean isMultiSet) {
            root = new Node<>();
            this.isMultiSet = isMultiSet;
        }

        public int size() {
            return root.size;
        }

        private Node<T> rotate(Node<T> a, boolean flag) {
            int d = 0;
            if (flag) d = 1;
            Node<T> b = a.ch[1 - d];
            a.ch[1 - d] = b.ch[d];
            b.ch[d] = a;
            b.size = a.size;
            a.size = a.ch[0].size + a.ch[1].size + 1;
            return b;
        }

        private Node<T> maintain(Node<T> n, boolean flag) {
            if (n.size == 0) return n;
            int d = 0;
            if (flag) d = 1;
            if (n.ch[d].size > 0 && n.ch[d].ch[d].size > n.ch[1 - d].size) {
                n = rotate(n, !flag);
            } else if (n.ch[d].size > 0 && n.ch[d].ch[1 - d].size > n.ch[1 - d].size) {
                n.ch[d] = rotate(n.ch[d], flag);
                n = rotate(n, !flag);
            } else
                return n;
            n.ch[1] = maintain(n.ch[1], true);
            n.ch[0] = maintain(n.ch[0], false);
            n = maintain(n, true);
            n = maintain(n, false);
            return n;
        }

        private Node<T> add(Node<T> n, T key) {
            if (n.size == 0) {
                n = new Node<>(key);
                return n;
            } else {
                ++n.size;
                int flag = n.key.compareTo(key);
                int d = 0;
                if (flag < 0) d = 1;
                n.ch[d] = add(n.ch[d], key);
                n = maintain(n, flag < 0);
            }
            return n;
        }

        public void add(T key) {
            if (!contains(key) || isMultiSet) root = add(root, key);
        }

        public boolean contains(T key) {
            Node<T> o = root;
            while (o.size > 0 && !o.key.equals(key)) {
                int flag = o.key.compareTo(key);
                int d = 0;
                if (flag < 0) d = 1;
                o = o.ch[d];
            }
            return o.size > 0;
        }

        public T getKth(int key) {
            for (Node<T> cur = root; ; ) {
                if (key <= cur.ch[0].size)
                    cur = cur.ch[0];
                else if (key == cur.ch[0].size + 1)
                    return cur.key;
                else {
                    key -= cur.ch[0].size + 1;
                    cur = cur.ch[1];
                }
            }
        }

        private class Node<T> {
            Node<T>[] ch = new Node[2];
            T key;
            int size;

            Node(T key) {
                this.key = key;
                this.size = 1;
                ch[1] = ch[0] = new Node<>();
            }

            Node() {
                key = null;
                size = 0;
            }

        }

    }

    static class InputReader extends InputStream {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

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

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 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 {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int length, int stIndex) {
            int[] arr = new int[length + stIndex];
            for (int i = stIndex; i < stIndex + length; i++)
                arr[i] = nextInt();
            return arr;
        }

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

    }

    static class MergeSort {
        private static final int CUTOFF = 7;

        private MergeSort() {
        }

        private static void swap(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }

        private static boolean less(Object a, Object b, Comparator comparator) {
            return comparator.compare(a, b) < 0;
        }

        private static void merge(Object[] src, Object[] dst, int lo, int mid, int hi, Comparator comparator) {
            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                if (i > mid) dst[k] = src[j++];
                else if (j > hi) dst[k] = src[i++];
                else if (less(src[j], src[i], comparator)) dst[k] = src[j++];
                else dst[k] = src[i++];
            }
        }

        private static void sort(Object[] src, Object[] dst, int lo, int hi, Comparator comparator) {
            if (hi <= lo + CUTOFF) {
                insertionSort(dst, lo, hi, comparator);
                return;
            }
            int mid = lo + (hi - lo) / 2;
            sort(dst, src, lo, mid, comparator);
            sort(dst, src, mid + 1, hi, comparator);
            if (!less(src[mid + 1], src[mid], comparator)) {
                System.arraycopy(src, lo, dst, lo, hi - lo + 1);
                return;
            }

            merge(src, dst, lo, mid, hi, comparator);
        }

        private static void insertionSort(Object[] a, int lo, int hi, Comparator comparator) {
            for (int i = lo; i <= hi; i++)
                for (int j = i; j > lo && less(a[j], a[j - 1], comparator); j--)
                    swap(a, j, j - 1);
        }

        public static void sort(Object[] a, int lo, int hi, Comparator comparator) {
            Object[] aux = a.clone();
            sort(aux, a, lo, hi, comparator);
        }

        public static int[] sort(int[] input, int lo, int hi, Comparator comparator) {
            Integer[] a = new Integer[input.length];
            for (int ctr = 0; ctr < input.length; ctr++) a[ctr] = input[ctr];
            sort(a, lo, hi, comparator);
            for (int ctr = 0; ctr < a.length; ctr++) input[ctr] = a[ctr];
            return input;
        }

    }

    static interface OrderedIterator<E> extends Iterator<E> {
    }

    static class TreeList<E> extends AbstractList<E> {
        private TreeList.AVLNode<E> root;
        private int size;

        public TreeList() {
            super();
        }

        public TreeList(final Collection<? extends E> coll) {
            super();
            if (!coll.isEmpty()) {
                root = new TreeList.AVLNode<>(coll);
                size = coll.size();
            }
        }

        public E get(final int index) {
            return root.get(index).getValue();
        }

        public int size() {
            return size;
        }

        public Iterator<E> iterator() {
            // override to go 75% faster
            return listIterator(0);
        }

        public ListIterator<E> listIterator() {
            // override to go 75% faster
            return listIterator(0);
        }

        public ListIterator<E> listIterator(final int fromIndex) {
            return new TreeList.TreeListIterator<>(this, fromIndex);
        }

        public int indexOf(final Object object) {
            // override to go 75% faster
            if (root == null) {
                return -1;
            }
            return root.indexOf(object, root.relativePosition);
        }

        public boolean contains(final Object object) {
            return indexOf(object) >= 0;
        }

        public Object[] toArray() {
            final Object[] array = new Object[size()];
            if (root != null) {
                root.toArray(array, root.relativePosition);
            }
            return array;
        }

        public void add(final int index, final E obj) {
            modCount++;
            if (root == null) {
                root = new TreeList.AVLNode<>(index, obj, null, null);
            } else {
                root = root.insert(index, obj);
            }
            size++;
        }

        public boolean addAll(final Collection<? extends E> c) {
            if (c.isEmpty()) {
                return false;
            }
            modCount += c.size();
            final TreeList.AVLNode<E> cTree = new TreeList.AVLNode<>(c);
            root = root == null ? cTree : root.addAll(cTree, size);
            size += c.size();
            return true;
        }

        public E set(final int index, final E obj) {
            final TreeList.AVLNode<E> node = root.get(index);
            final E result = node.value;
            node.setValue(obj);
            return result;
        }

        public E remove(final int index) {
            modCount++;
            final E result = get(index);
            root = root.remove(index);
            size--;
            return result;
        }

        public void clear() {
            modCount++;
            root = null;
            size = 0;
        }

        static class AVLNode<E> {
            private TreeList.AVLNode<E> left;
            private boolean leftIsPrevious;
            private TreeList.AVLNode<E> right;
            private boolean rightIsNext;
            private int height;
            private int relativePosition;
            private E value;

            private AVLNode(final int relativePosition, final E obj,
                            final TreeList.AVLNode<E> rightFollower, final TreeList.AVLNode<E> leftFollower) {
                this.relativePosition = relativePosition;
                value = obj;
                rightIsNext = true;
                leftIsPrevious = true;
                right = rightFollower;
                left = leftFollower;
            }

            private AVLNode(final Collection<? extends E> coll) {
                this(coll.iterator(), 0, coll.size() - 1, 0, null, null);
            }

            private AVLNode(final Iterator<? extends E> iterator, final int start, final int end,
                            final int absolutePositionOfParent, final TreeList.AVLNode<E> prev, final TreeList.AVLNode<E> next) {
                final int mid = start + (end - start) / 2;
                if (start < mid) {
                    left = new TreeList.AVLNode<>(iterator, start, mid - 1, mid, prev, this);
                } else {
                    leftIsPrevious = true;
                    left = prev;
                }
                value = iterator.next();
                relativePosition = mid - absolutePositionOfParent;
                if (mid < end) {
                    right = new TreeList.AVLNode<>(iterator, mid + 1, end, mid, this, next);
                } else {
                    rightIsNext = true;
                    right = next;
                }
                recalcHeight();
            }

            E getValue() {
                return value;
            }

            void setValue(final E obj) {
                this.value = obj;
            }

            TreeList.AVLNode<E> get(final int index) {
                final int indexRelativeToMe = index - relativePosition;

                if (indexRelativeToMe == 0) {
                    return this;
                }

                final TreeList.AVLNode<E> nextNode = indexRelativeToMe < 0 ? getLeftSubTree() : getRightSubTree();
                if (nextNode == null) {
                    return null;
                }
                return nextNode.get(indexRelativeToMe);
            }

            int indexOf(final Object object, final int index) {
                if (getLeftSubTree() != null) {
                    final int result = left.indexOf(object, index + left.relativePosition);
                    if (result != -1) {
                        return result;
                    }
                }
                if (value == null ? value == object : value.equals(object)) {
                    return index;
                }
                if (getRightSubTree() != null) {
                    return right.indexOf(object, index + right.relativePosition);
                }
                return -1;
            }

            void toArray(final Object[] array, final int index) {
                array[index] = value;
                if (getLeftSubTree() != null) {
                    left.toArray(array, index + left.relativePosition);
                }
                if (getRightSubTree() != null) {
                    right.toArray(array, index + right.relativePosition);
                }
            }

            TreeList.AVLNode<E> next() {
                if (rightIsNext || right == null) {
                    return right;
                }
                return right.min();
            }

            TreeList.AVLNode<E> previous() {
                if (leftIsPrevious || left == null) {
                    return left;
                }
                return left.max();
            }

            TreeList.AVLNode<E> insert(final int index, final E obj) {
                final int indexRelativeToMe = index - relativePosition;

                if (indexRelativeToMe <= 0) {
                    return insertOnLeft(indexRelativeToMe, obj);
                }
                return insertOnRight(indexRelativeToMe, obj);
            }

            private TreeList.AVLNode<E> insertOnLeft(final int indexRelativeToMe, final E obj) {
                if (getLeftSubTree() == null) {
                    setLeft(new TreeList.AVLNode<>(-1, obj, this, left), null);
                } else {
                    setLeft(left.insert(indexRelativeToMe, obj), null);
                }

                if (relativePosition >= 0) {
                    relativePosition++;
                }
                final TreeList.AVLNode<E> ret = balance();
                recalcHeight();
                return ret;
            }

            private TreeList.AVLNode<E> insertOnRight(final int indexRelativeToMe, final E obj) {
                if (getRightSubTree() == null) {
                    setRight(new TreeList.AVLNode<>(+1, obj, right, this), null);
                } else {
                    setRight(right.insert(indexRelativeToMe, obj), null);
                }
                if (relativePosition < 0) {
                    relativePosition--;
                }
                final TreeList.AVLNode<E> ret = balance();
                recalcHeight();
                return ret;
            }

            private TreeList.AVLNode<E> getLeftSubTree() {
                return leftIsPrevious ? null : left;
            }

            private TreeList.AVLNode<E> getRightSubTree() {
                return rightIsNext ? null : right;
            }

            private TreeList.AVLNode<E> max() {
                return getRightSubTree() == null ? this : right.max();
            }

            private TreeList.AVLNode<E> min() {
                return getLeftSubTree() == null ? this : left.min();
            }

            TreeList.AVLNode<E> remove(final int index) {
                final int indexRelativeToMe = index - relativePosition;

                if (indexRelativeToMe == 0) {
                    return removeSelf();
                }
                if (indexRelativeToMe > 0) {
                    setRight(right.remove(indexRelativeToMe), right.right);
                    if (relativePosition < 0) {
                        relativePosition++;
                    }
                } else {
                    setLeft(left.remove(indexRelativeToMe), left.left);
                    if (relativePosition > 0) {
                        relativePosition--;
                    }
                }
                recalcHeight();
                return balance();
            }

            private TreeList.AVLNode<E> removeMax() {
                if (getRightSubTree() == null) {
                    return removeSelf();
                }
                setRight(right.removeMax(), right.right);
                if (relativePosition < 0) {
                    relativePosition++;
                }
                recalcHeight();
                return balance();
            }

            private TreeList.AVLNode<E> removeMin() {
                if (getLeftSubTree() == null) {
                    return removeSelf();
                }
                setLeft(left.removeMin(), left.left);
                if (relativePosition > 0) {
                    relativePosition--;
                }
                recalcHeight();
                return balance();
            }

            private TreeList.AVLNode<E> removeSelf() {
                if (getRightSubTree() == null && getLeftSubTree() == null) {
                    return null;
                }
                if (getRightSubTree() == null) {
                    if (relativePosition > 0) {
                        left.relativePosition += relativePosition;
                    }
                    left.max().setRight(null, right);
                    return left;
                }
                if (getLeftSubTree() == null) {
                    right.relativePosition += relativePosition - (relativePosition < 0 ? 0 : 1);
                    right.min().setLeft(null, left);
                    return right;
                }

                if (heightRightMinusLeft() > 0) {
                    // more on the right, so delete from the right
                    final TreeList.AVLNode<E> rightMin = right.min();
                    value = rightMin.value;
                    if (leftIsPrevious) {
                        left = rightMin.left;
                    }
                    right = right.removeMin();
                    if (relativePosition < 0) {
                        relativePosition++;
                    }
                } else {
                    // more on the left or equal, so delete from the left
                    final TreeList.AVLNode<E> leftMax = left.max();
                    value = leftMax.value;
                    if (rightIsNext) {
                        right = leftMax.right;
                    }
                    final TreeList.AVLNode<E> leftPrevious = left.left;
                    left = left.removeMax();
                    if (left == null) {
                        // special case where left that was deleted was a double link
                        // only occurs when height difference is equal
                        left = leftPrevious;
                        leftIsPrevious = true;
                    }
                    if (relativePosition > 0) {
                        relativePosition--;
                    }
                }
                recalcHeight();
                return this;
            }

            private TreeList.AVLNode<E> balance() {
                switch (heightRightMinusLeft()) {
                    case 1:
                    case 0:
                    case -1:
                        return this;
                    case -2:
                        if (left.heightRightMinusLeft() > 0) {
                            setLeft(left.rotateLeft(), null);
                        }
                        return rotateRight();
                    case 2:
                        if (right.heightRightMinusLeft() < 0) {
                            setRight(right.rotateRight(), null);
                        }
                        return rotateLeft();
                    default:
                        throw new RuntimeException("tree inconsistent!");
                }
            }

            private int getOffset(final TreeList.AVLNode<E> node) {
                if (node == null) {
                    return 0;
                }
                return node.relativePosition;
            }

            private int setOffset(final TreeList.AVLNode<E> node, final int newOffest) {
                if (node == null) {
                    return 0;
                }
                final int oldOffset = getOffset(node);
                node.relativePosition = newOffest;
                return oldOffset;
            }

            private void recalcHeight() {
                height = Math.max(
                        getLeftSubTree() == null ? -1 : getLeftSubTree().height,
                        getRightSubTree() == null ? -1 : getRightSubTree().height) + 1;
            }

            private int getHeight(final TreeList.AVLNode<E> node) {
                return node == null ? -1 : node.height;
            }

            private int heightRightMinusLeft() {
                return getHeight(getRightSubTree()) - getHeight(getLeftSubTree());
            }

            private TreeList.AVLNode<E> rotateLeft() {
                final TreeList.AVLNode<E> newTop = right; // can't be faedelung!
                final TreeList.AVLNode<E> movedNode = getRightSubTree().getLeftSubTree();

                final int newTopPosition = relativePosition + getOffset(newTop);
                final int myNewPosition = -newTop.relativePosition;
                final int movedPosition = getOffset(newTop) + getOffset(movedNode);

                setRight(movedNode, newTop);
                newTop.setLeft(this, null);

                setOffset(newTop, newTopPosition);
                setOffset(this, myNewPosition);
                setOffset(movedNode, movedPosition);
                return newTop;
            }

            private TreeList.AVLNode<E> rotateRight() {
                final TreeList.AVLNode<E> newTop = left;
                final TreeList.AVLNode<E> movedNode = getLeftSubTree().getRightSubTree();

                final int newTopPosition = relativePosition + getOffset(newTop);
                final int myNewPosition = -newTop.relativePosition;
                final int movedPosition = getOffset(newTop) + getOffset(movedNode);

                setLeft(movedNode, newTop);
                newTop.setRight(this, null);

                setOffset(newTop, newTopPosition);
                setOffset(this, myNewPosition);
                setOffset(movedNode, movedPosition);
                return newTop;
            }

            private void setLeft(final TreeList.AVLNode<E> node, final TreeList.AVLNode<E> previous) {
                leftIsPrevious = node == null;
                left = leftIsPrevious ? previous : node;
                recalcHeight();
            }

            private void setRight(final TreeList.AVLNode<E> node, final TreeList.AVLNode<E> next) {
                rightIsNext = node == null;
                right = rightIsNext ? next : node;
                recalcHeight();
            }

            private TreeList.AVLNode<E> addAll(TreeList.AVLNode<E> otherTree, final int currentSize) {
                final TreeList.AVLNode<E> maxNode = max();
                final TreeList.AVLNode<E> otherTreeMin = otherTree.min();

                // We need to efficiently merge the two AVL trees while keeping them
                // balanced (or nearly balanced). To do this, we take the shorter
                // tree and combine it with a similar-height subtree of the taller
                // tree. There are two symmetric cases:
                //   * this tree is taller, or
                //   * otherTree is taller.
                if (otherTree.height > height) {
                    // CASE 1: The other tree is taller than this one. We will thus
                    // merge this tree into otherTree.

                    // STEP 1: Remove the maximum element from this tree.
                    final TreeList.AVLNode<E> leftSubTree = removeMax();

                    // STEP 2: Navigate left from the root of otherTree until we
                    // contains a subtree, s, that is no taller than me. (While we are
                    // navigating left, we store the nodes we encounter in a stack
                    // so that we can re-balance them in step 4.)
                    final Deque<TreeList.AVLNode<E>> sAncestors = new ArrayDeque<>();
                    TreeList.AVLNode<E> s = otherTree;
                    int sAbsolutePosition = s.relativePosition + currentSize;
                    int sParentAbsolutePosition = 0;
                    while (s != null && s.height > getHeight(leftSubTree)) {
                        sParentAbsolutePosition = sAbsolutePosition;
                        sAncestors.push(s);
                        s = s.left;
                        if (s != null) {
                            sAbsolutePosition += s.relativePosition;
                        }
                    }

                    // STEP 3: Replace s with a newly constructed subtree whose root
                    // is maxNode, whose left subtree is leftSubTree, and whose right
                    // subtree is s.
                    maxNode.setLeft(leftSubTree, null);
                    maxNode.setRight(s, otherTreeMin);
                    if (leftSubTree != null) {
                        leftSubTree.max().setRight(null, maxNode);
                        leftSubTree.relativePosition -= currentSize - 1;
                    }
                    if (s != null) {
                        s.min().setLeft(null, maxNode);
                        s.relativePosition = sAbsolutePosition - currentSize + 1;
                    }
                    maxNode.relativePosition = currentSize - 1 - sParentAbsolutePosition;
                    otherTree.relativePosition += currentSize;

                    // STEP 4: Re-balance the tree and recalculate the heights of s's ancestors.
                    s = maxNode;
                    while (!sAncestors.isEmpty()) {
                        final TreeList.AVLNode<E> sAncestor = sAncestors.pop();
                        sAncestor.setLeft(s, null);
                        s = sAncestor.balance();
                    }
                    return s;
                }
                otherTree = otherTree.removeMin();

                final Deque<TreeList.AVLNode<E>> sAncestors = new ArrayDeque<>();
                TreeList.AVLNode<E> s = this;
                int sAbsolutePosition = s.relativePosition;
                int sParentAbsolutePosition = 0;
                while (s != null && s.height > getHeight(otherTree)) {
                    sParentAbsolutePosition = sAbsolutePosition;
                    sAncestors.push(s);
                    s = s.right;
                    if (s != null) {
                        sAbsolutePosition += s.relativePosition;
                    }
                }

                otherTreeMin.setRight(otherTree, null);
                otherTreeMin.setLeft(s, maxNode);
                if (otherTree != null) {
                    otherTree.min().setLeft(null, otherTreeMin);
                    otherTree.relativePosition++;
                }
                if (s != null) {
                    s.max().setRight(null, otherTreeMin);
                    s.relativePosition = sAbsolutePosition - currentSize;
                }
                otherTreeMin.relativePosition = currentSize - sParentAbsolutePosition;

                s = otherTreeMin;
                while (!sAncestors.isEmpty()) {
                    final TreeList.AVLNode<E> sAncestor = sAncestors.pop();
                    sAncestor.setRight(s, null);
                    s = sAncestor.balance();
                }
                return s;
            }

        }

        static class TreeListIterator<E> implements ListIterator<E>, OrderedIterator<E> {
            private final TreeList<E> parent;
            private TreeList.AVLNode<E> next;
            private int nextIndex;
            private TreeList.AVLNode<E> current;
            private int currentIndex;
            private int expectedModCount;

            private TreeListIterator(final TreeList<E> parent, final int fromIndex) throws IndexOutOfBoundsException {
                super();
                this.parent = parent;
                this.expectedModCount = parent.modCount;
                this.next = parent.root == null ? null : parent.root.get(fromIndex);
                this.nextIndex = fromIndex;
                this.currentIndex = -1;
            }

            private void checkModCount() {
                if (parent.modCount != expectedModCount) {
                    throw new ConcurrentModificationException();
                }
            }

            public boolean hasNext() {
                return nextIndex < parent.size();
            }

            public E next() {
                checkModCount();
                if (!hasNext()) {
                    throw new NoSuchElementException("No element at index " + nextIndex + ".");
                }
                if (next == null) {
                    next = parent.root.get(nextIndex);
                }
                final E value = next.getValue();
                current = next;
                currentIndex = nextIndex++;
                next = next.next();
                return value;
            }

            public boolean hasPrevious() {
                return nextIndex > 0;
            }

            public E previous() {
                checkModCount();
                if (!hasPrevious()) {
                    throw new NoSuchElementException("Already at start of list.");
                }
                if (next == null) {
                    next = parent.root.get(nextIndex - 1);
                } else {
                    next = next.previous();
                }
                final E value = next.getValue();
                current = next;
                currentIndex = --nextIndex;
                return value;
            }

            public int nextIndex() {
                return nextIndex;
            }

            public int previousIndex() {
                return nextIndex() - 1;
            }

            public void remove() {
                checkModCount();
                if (currentIndex == -1) {
                    throw new IllegalStateException();
                }
                parent.remove(currentIndex);
                if (nextIndex != currentIndex) {
                    // remove() following next()
                    nextIndex--;
                }
                // the AVL node referenced by next may have become stale after a remove
                // reset it now: will be retrieved by next call to next()/previous() via nextIndex
                next = null;
                current = null;
                currentIndex = -1;
                expectedModCount++;
            }

            public void set(final E obj) {
                checkModCount();
                if (current == null) {
                    throw new IllegalStateException();
                }
                current.setValue(obj);
            }

            public void add(final E obj) {
                checkModCount();
                parent.add(nextIndex, obj);
                current = null;
                currentIndex = -1;
                nextIndex++;
                expectedModCount++;
            }

        }

    }

    static class MaxMin {
        public static <T extends Comparable<T>> T Max(T x, T y) {
            T max = x;
            if (y.compareTo(max) > 0) max = y;
            return max;
        }

        public static <T extends Comparable<T>> T Min(T x, T y) {
            T min = x;
            if (y.compareTo(min) < 0) min = y;
            return min;
        }

    }
}

