#include <cstdio>
#include <cassert>


using namespace std;

typedef int T;
const int MAX=1000;
const int NONE=-1;

struct Item{
  int prev;
  int next;
  T value;
  
  
  Item(int a_prev, int a_next, T a_value){
    prev=a_prev;
    next=a_next;
    value=a_value;
  }
  
  Item(T a_value){
    prev=NONE;
    next=NONE;
    value=a_value;
  }
  
  Item(){
    prev=NONE;
    next=NONE;
    value=0;
  }
  
};
  

class List_Iterator{
  Item** items;
  int* first;
  int* last;
  int cur;
  public:
  
  
  List_Iterator(Item** a_items, int* a_first, int* a_last){
    items = a_items;
    first = a_first;
    last  = a_last;
    cur   = *a_first;
    
  }
  
    
  void begin(){
    cur=*first;
  }
  
  void end(){
    cur=*last;
  }
  
  bool next(){
    if(cur!=NONE){
      if(items[cur]->next == NONE)
        return false;    
      else
        cur=items[cur]->next;
    }
    return (cur!=NONE);
  }
  
  bool prev(){
    if(cur!=NONE)
      if(items[cur]->prev == NONE)
        return false;    
      else
        cur=items[cur]->prev;
    return (cur!=NONE); 
  }
  
  T get(){
    if(cur!=NONE)
      return items[cur]->value;
    return 0;
  }
  
  
  
};




class List{

    Item* items[MAX];
    int first;       //индекс начального элемента
    int last;        //индекс конечного элемента
    int num;         //общее число элементов
     
     
    //ищем следующее свободное место в массиве
    int get_free_index(){
      int i=0;
      for(i=0;i<MAX;i++){
       if( items[i]->prev==NONE && items[i]->next==NONE ){      
            return i+(num==1);
       }
      }
      
      return NONE;

    }

    //вставляем значение перед выбранным элементом массива
    void insert_before(int i, T a_value){
      if(isEmpty()){
        add(a_value);
        return;
      }
      
      int free_index=get_free_index();
      
      items[free_index]       = new Item(a_value);
      
      items[free_index]->next = i;
      items[free_index]->prev = items[i]->prev;

      if(i!=first){
          items[items[i]->prev]->next=free_index;
      }

      items[i]->prev          = free_index;
      

      
      if(i == first)
        first=free_index;
      
      num++;
      
    }

    
    
    //ищем и возвращаем индекс элемента в массиве, чье значение равно аргументу
    int findItem(T value){
      if(isEmpty()) return NONE;
      //будем возвращать первый найденный индекс
      
      int i = first;
      
      while(items[i]->next != NONE && items[i]->value != value){
        i=items[i]->next;
      }
      
      if(items[i]->value == value)
        return i;

      return NONE;
    }

    //получить индекс на элемент по номеру его в списке
    int getItem(unsigned int index){
      if(isEmpty())      return NONE;
      if(index==0)       return first;
      if(index==(num-1)) return last;
      if(index>=num)     return NONE; 
      
      int i;

      //определяем с какого конца легче двигатся
      if(index>=num/2){
        i=last;
        index=num-index-1;
        while(index){
          i=items[i]->prev;
          index--;
        }
      }
      else{
        i=first;
        while(index){
          i=items[i]->next;
          index--;
        }
      }
      
      return i;
    }

    //удаляем элемент по его номеру в массиве
    void removeItem(int i){
      if(isEmpty()) return;
      
      if(items[i]->prev != NONE)
        items[items[i]->prev]->next=items[i]->next;
        
      if(items[i]->next != NONE)
        items[items[i]->next]->prev=items[i]->prev;


      num--;
      
      if(i == first){
          first=items[i]->next;
      }    
      

      if(i == last){
          last=items[i]->prev;        
      }
      
      items[i]->prev=NONE;
      items[i]->next=NONE;
      
      
      if(!num){
        first=0;
        last=0;
      }
      

    }

    public:
    List (){
      clear();      
    }
    
    ~List (){
      clear();     
    }
    
    // добавить в конец
    void add(T value){
      int free_index=get_free_index();
      items[free_index] = new Item(value);
      if(!num){
        first = free_index;
        last  = free_index;
      }
      else{
        items[free_index]->prev = last;
        items[last]      ->next = free_index;
        last                    = free_index;
      }
      num++;
    }
    
    // добавить элемент в позицию с указанным индексом
    void insert(unsigned int index, T a_value){
      //будем добавлять перед этим эл-том
      //cначало досчитаем до этого элемента
      
      if(!index)
        return insert_before(first, a_value);
        
      //если индекс превышает число эл-тов то добавляем в конец
      if(index>num)
        return add(a_value);
      
      int i;
      
     
      //определяем с какого конца легче двигатся
      if(index>=num/2){
        i=last;
        index=num-index-1;
        while(index){
          i=items[i]->prev;
          index--;
        }
      }
      else{
        i=first;
        while(index){
          i=items[i]->next;
          index--;
        }
      }
      return insert_before(i,a_value);
    }
    
    // установить значение по индексу 
    void set(int index, T value){
      int i = getItem(index);
      items[i]->value=value;
    };
    
    
    
    // получить значение по индексу
    T get(int index){
      int i=getItem(index);
      if(i!=NONE)
        return items[i]->value;
      return NONE;
    }
    
    // очистить список 
    void clear (){
      num=0;
      first=0;
      last=0;
      for(int i=0;i<MAX;i++){
        items[i]=new Item;
      }
    }
    
    // получить количество 
    int count(){
      return num;
    }
    
    // пустой ли список 
    bool isEmpty(){
      return !num;
    }
    
    // получить индекс указаного элемента. Если: элемента нет, вернуть -1
    int indexOf(T value){
      if(isEmpty()) return NONE;
      
      //будем возвращать первый найденный индекс
      int i=first;
      int j=0;
      while(items[i]->next != NONE && items[i]->value != value){
        i=items[i]->next;
        j++;
      }
      
      if(items[i]->value == value)
        return j;

      
      return NONE;
      
    }
    
    // проверить, принадлежит ли элемент списку
    bool contains(T value){
      return (bool)(indexOf(value)+1);
    }
    
    // удалить все вхождения элемента из списка
    void remove(T value){
      if(isEmpty()) return;
      while(true){
        int i=findItem(value);
        
        if(i==NONE)
          break;
          
        removeItem(i);
      }
        
      
      
    }
    
    // удалить элемент с заданным индексом
    void removeAt(int index){
      if(isEmpty()) return;
      int i=getItem(index);
      if(i!=NONE)
        removeItem(i);
      
    }
    
    
    
    void print(){
      int i=first,j=0;
      printf("\n\n  Count elements: %i \n", num);
      //printf("  First index: %i \n",first);
      //printf("  Last index: %i \n",last);
      printf("--------------------------------------------------------------------------------");
      printf("  index  |  prev  |  next  |    value    |  arr_key  \n");
      for(int j=0;j<num;j++){
        
        printf("  %4i   |  %3i   |  %3i   |  %9i  |   %3i \n",j,items[i]->prev,items[i]->next, items[i]->value, i);
        i=items[i]->next;
      }
      printf("--------------------------------------------------------------------------------\n");
      
    }
    
    


    // скопировать список в массив (предполагается, что массив содержит достаточное количество элементов для выполнения операции) 
    void copyTo(T* arr){
      int i=first;
      for(int j=0;j<num;j++){
        arr[j] = items[i]->value;
        i      = items[i]->next;
      }
    }
    
    // получить итератор для обхода спискa
    List_Iterator* getIterator(){
      return new List_Iterator(items,&first,&last);
      
    }


};


void task(){
  
  
  
}


void test(){
    List* list = new List();
    
    /*тестирование на пустоту*/
    assert(list->isEmpty() ) ;
    assert(list->count() == 0);

    /*тестирование на дополнение в конец, изменение числа элементов, наличие элементов */
    for(int i=0;i<10;i++){
      list->add(i);
      assert(!list->isEmpty());
      assert(list->get(i)==i);
      assert(list->count() == i+1);
      
      assert(list->contains(i));
      assert(list->indexOf(i)==i);
      
      assert(!list->contains(i+1));
      assert(list->indexOf(i+1)==NONE);
    }
    
    
    /*Тестирование удаления по значению*/
    for(int i=0;i<10;i+=2){
      list->remove(i);
      assert(list->count() == 10-i/2-1);
      assert(!list->contains(i));
    }

    /*Тестирование удаления по номеру элемента в списке*/    
    list->removeAt(4);
    list->removeAt(3);
    list->removeAt(2);
    list->removeAt(1);
    list->removeAt(0);

    assert(list->isEmpty()) ;
    assert(list->count() == 0);

    /*Тестирование вставки в начало*/
    for(int i=1;i<10;i++){
      list->insert(0,i);
    }
    
    /*Тестирование очистки*/
    list->clear();
    assert(list->isEmpty() ) ;
    assert(list->count() == 0);
    
    /*Тестирование удаления одинаковых элементов*/
    for(int i=0;i<100;i++)
      list->add(486);
    list->remove(486);
    assert(list->isEmpty() ) ;
    assert(list->count() == 0);

    /*Тестирование изменения*/
    list->add(1);
    assert(list->get(0)==1);
    list->set(0,31337);
    assert(list->get(0)==31337);
    list->clear();
    
    /*Тестирование вставки элемента на место выбранного*/
    list->add(0);
    list->add(1);
    assert(list->get(1)==1);
    list->insert(1,2);
    assert(list->get(1)==2);
    list->insert(2,3);
    assert(list->get(2)==3);
    list->insert(2,4);
    assert(list->get(2)==4);
    list->clear();
    
    /*Тестирование итератора*/
    
    //заполняем список
    for(int i=0;i<10;i++){
      list->add(i);
    }
    
    //просим итератор
    List_Iterator* it=list->getIterator();
    
    
    it->begin(); //ставим итератор на начало
    assert(!it->prev()); //сзади элементов нету
    
    int i=0;
    
    
    //обходим вперед
    do{  
      assert(it->get()==i);
      i++;
    }while(it->next());
    
    
    it->end(); //cтавим итератор в конец
    assert(!it->next()); //впереди элементов нету

    i=9;
    do{  
      assert(it->get()==i);
      i--;
    }while(it->prev());
    
    delete(it);
    delete(list);


    printf("Все тесты пройдены!\n");

}

void print_menu_header(){
  printf("1 - Напечатать список\n");
  
  printf("2 - Вставка элемента в начало\n");
  printf("3 - Вставка элемента в конец\n");
  printf("4 - Вставка элемента перед заданным элементом\n");
  
  printf("5 - Удаление элемента по индексу\n");  
  printf("6 - Удаление элемента по значению\n");  
  
  printf("7 - Вывод числа элементов\n");
  printf("8 - Добавить k экземпляров последнего элемента в начало списка\n");
  
  printf("9 - Выход\n\n");
}



int main(){
  int command=0;
  int i,j;
  test();
  
  List* list = new List();
  
  while(true){
    print_menu_header();
    scanf("%i", &command);
    
    
    switch(command){
      case 1:
        list->print();
      break;
      
      case 2:
        printf("Введите элемент: ");
        scanf("%i",&i);
        list->insert(0,i);
      break;

      case 3:
        printf("Введите элемент: ");
        scanf("%i",&i);
        list->add(i);
      break;
      
      case 4:
        printf("Введите элемент перед который хотите вставить: ");
        scanf("%i",&j);
        printf("Введите элемент для вставки: ");
        scanf("%i",&i); 
        list->insert(j,i);
      break;

      case 5:
        printf("Введите номер элемента для удаления (индексация с нуля): ");
        scanf("%i",&j);
        list->removeAt(j);
      break;
      
      case 6:
        printf("Введите значение элемента для удаления: ");
        scanf("%i",&i);
        list->remove(i);
      break;      
      
      case 7:
        printf("В списке %i элементов\n",list->count());
      break;   

      case 8:
        printf("Введите число повторений: ");
        scanf("%i",&j);
        i=list->get(list->count()-1);
        for(;j>0;j--)
          list->insert(0,i);
        
        
      break;   
           
      case 9:
        return 0;
      
           
    }
    
  }
  

  return 0;
}