public class Main {

    private static class List {
        private List next;
        private List previous;
        private int value;

        public List() {
            next = null;
            previous = null;
        }

        public List(int[] array) {
            value = array[0];
            List node = this;
            for (int i = 1; i < array.length; i += 1) {
                node.next = new List();
                node.next.previous = node;
                node = node.next;
                node.value = array[i];
            }
        }

        public List get(int index) throws IndexOutOfBoundsException {
            if (index < 0) {
                throw new IndexOutOfBoundsException();
            }
            List node = this;
            for (int i = 0; i < index; i += 1) {
                if (node.next != null) {
                    node = node.next;
                } else {
                    throw new IndexOutOfBoundsException();
                }
            }
            return node;
        }

        public void deletePrevious() {
            previous = previous.previous;
        }

        public void setNext(List node) {
            next = node;
        }

        public int getValue() {
            return value;
        }

        public List getNext() {
            if (next == null) {
                throw new IndexOutOfBoundsException();
            }
            return next;
        }

        public List getPrevious() {
            if (previous == null) {
                throw new IndexOutOfBoundsException();
            }
            return previous;
        }

        public void print() {
            System.out.print(value + " ");
            if (next != null) {
                next.print();
            }
        }
    }

    private static int[] sell(int[] giftsArray, int[] customers) {
        int[] sales = new int[customers.length];
        List gifts = new List(giftsArray);
        List gift = gifts.get(0);
        boolean outOfStock = false;
        for (int m = 0; m < customers.length; m += 1) {
            if (outOfStock) {
                return sales;
            }
            while (true) {
                if (gift.getValue() <= customers[m]) {
                    try {
                        gift = gift.getNext();
                    } catch (IndexOutOfBoundsException e0) {
                        // if next does not exist then there is no
                        // gift more expensive, thus, the customer
                        // must buy this gift
                        sales[m] = gift.getValue();
                        try {
                            gift = gift.getPrevious();
                        } catch (IndexOutOfBoundsException e1) {
                            // if there is no previous gift, then
                            // the shop has run out of gifts to sell
                            outOfStock = true;
                            break;
                        }
                        gift.setNext(null);
                        break;
                    }
                } else {
                    // try to sell previous gift
                    try {
                        sales[m] = gift.getPrevious().getValue();
                        gift.deletePrevious();
                    } catch (IndexOutOfBoundsException e) {
                        // if previous does not exist, there is no gift
                        // which this customer can afford
                        sales[m] = 0;
                    }
                    break;
                }
            }
        }
        return sales;
    }

    public static void main(String[] args) {
        int[] gifts = {1, 2, 2, 2, 5, 7, 10, 20};
        int[] customers = {1,1,2,3,6,6,15,21,21,22};

        int[] sales = sell(gifts, customers);
        for (int sale : sales) {
            System.out.print(sale +  " ");
        }
        System.out.println();
    }
}