// Вариант 6
//Pivot index
// Найти элемент, для которого сумма всех элементов справа будет равна сумме всех элементов слева.
        public int pivotIndex(int[] nums) {
            int right = 0;
            int left = 0;
//Находим сумму элементов справа, а потом при движении по массиву,
//отнимаем от нее действительный(на котором мы сейчас находимся) элемент,
//и прибавляя прошлый к левой части.
            for(int i = 0; i < nums.length; i++){
                right += nums[i];
            }
            for(int i = 0; i < nums.length; i++){
                if(i != 0){
                    left += nums[i-1];
                }
                right -= nums[i];
                if(right == left){
                    return i;
                }
            }
            return -1;
        }

// 2.   Список з нулів і одиничок потрібно переупорядкувати так що нулі були спочатку
// Я сделал двонаправленный
// 0 and 1
        private static DLNode order(DLNode head) {
            DLNode pres = head;
            DLNode zero = null;
            DLNode one = null;
            DLNode tmp = null;
            while(pres != null) {
                    //Delete
                    if (pres.next != null) {
                        pres.next.prev = pres.prev;
                    }
                    tmp = pres;
                    //Move
                    pres = pres.next;
                    tmp.next = null;
                    //Add in the end
                    if(tmp.data == 0) {
                        zero = addInTheEnd(zero, tmp);
                    }
                    else {
                        one = addInTheEnd(one, tmp);
                    }
            }
            //Connection
            zero = addInTheEnd(zero, one);
            return zero;
        }
// Дополнительная функция
    private static DLNode addInTheEnd(DLNode head, DLNode node) {
            if(head == null) {
                return node;
            }
            if(node == null) {
                return head;
            }
            DLNode tail = head;
            while(tail.next != null) {
                tail = tail.next;
            }
            tail.next = node;
            node.prev = tail;
            return head;
        }


// Вариант 7
// Найти количество вхождений через бинарку
        public static int frequency(char ar[], char x) {
            //Sort
            SelectionSort(ar);
            //Search
            int firstIndex = binFirst(ar, x);
            //Counting
            int count = 0;
            if(firstIndex != -1) {
                // If firstIndex == ar.length, we will go beyond the array
                while(firstIndex != ar.length && ar[firstIndex] == x) {
                    count++;
                    firstIndex++;
                }
            }
            // Visual check
            System.out.println("In this array");
            printList(ar);
            System.out.printf("Symbol \"" + x + "\" is repeated " + count + " times");

            return count;
        }
//Дополнительные функции
public static void SelectionSort(char [] ar) {

            char tmp = 0;
            // sorting
            for (int i = 0; i < ar.length - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < ar.length; j++) {
                    if (ar[j] < ar[minIndex]) {
                        minIndex = j;
                    }
                }
                if (i != minIndex) {
                    tmp = ar[i];
                    ar[i] = ar[minIndex];
                    ar[minIndex] = tmp;
                }
            }
        }

public static int binFirst(char ar[], char x) {
            int l = 0;
            int h = ar.length - 1;
            while(h >= l) {
                int mid = (l + h)/2;
                if((mid == 0 || x > ar[mid-1]) && ar[mid] == x)
                    return mid;
                else if (x > ar[mid])
                    l = mid + 1;
                else
                    h = mid - 1;
            }
            return -1;
        }

private static void printList(char [] array) {
            if(array.length == 0) {
                System.out.println("Your Array is empty.");
            }else {
                for(int i = 0; i <  array.length; i++) {
                    System.out.printf(array[i] + " ");
                }
            }
            System.out.println("");
        }

// Сорт выборкой двонаправленного списка с фиктивными узлами
//  Selection sort (взято у Хоменко)
        private static DLNode selectionSort(DLNode h) {

            DLNode s = null; // head of sorted list
            //Гениально...
            h = DelFict(h);
            while (h != null) {

                // find the node with maximum value in the unsorted list
                DLNode max = maxNode(h);
                // remove the node with maximum value from unsorted list
                h = remove(h, max);
                // insert the node with maximum value at the front of sorted list
                s = addFirst(s, max);
            }
            s = makeFictList(s);
            return s;
        }
//Дополнительные функции
//Delete a fict
        public static DLNode DelFict(DLNode h) {
            if(h == null) return h;
            if(h.prev == null) return h;
            h.prev.prev.next = null;
            h.prev = null;
            return h;
        }

    public static DLNode maxNode(DLNode h) {
            if (h == null || h.data == FICT_NUMBER)
                return h;
            else {
                DLNode max = h;
                DLNode cur = h;
                while (cur != null && cur.data != FICT_NUMBER) {
                    if (cur.data > max.data) {
                        max = cur;
                    }
                    cur = cur.next;
                }
                return max;
            }
        }

        public static DLNode remove(DLNode h, DLNode x) {
            // check if x is the head
            if (x.prev != null) {
                x.prev.next = x.next;
            } else {
                h = h.next;
            }
            // check if x is the tail
            if (x.next != null) {
                x.next.prev = x.prev;
            }
            return h;
        }

public static DLNode addFirst(DLNode h, DLNode newNode) {
            newNode.prev = null;
            newNode.next = h;
            if (h != null) {
                h.prev = newNode;
            }
            return newNode;
        }

        public static DLNode makeFictList(DLNode h) {
            DLNode fict = createDLNode(FICT_NUMBER);
            DLNode tail = tailSearch(h);
            tail.next = fict;
            fict.prev = tail;
            h.prev = fict;
            fict.next = h;
            return h;
        }

        public static DLNode tailSearch(DLNode h) {
            if (h == null)
                return h;
            DLNode t = h;
            while(t.next != null) {
                t = t.next;
            }
            return t;
        }