#include <cstdio>
#include <cassert>


using namespace std;

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

class List{
    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;
      }
      
    };
  
    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){
      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;
      items[i]->prev          = free_index;
      
      if(i == first)
        first=free_index;
      
      num++;
      
    }


    void insert_after(int i, T a_value){
      int free_index=get_free_index();
      
      items[free_index]       = new Item(a_value);
      items[free_index]->prev = i;
      
      items[free_index]->next = items[i]->next;
      
      if(items[i]->next!=NONE)
        items[items[i]->next]->prev=free_index;
      
      
      items[i]->next          = free_index;
      
      if(i == last)
        last=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 (){
      num=0;
      first=0;
      last=0;
      for(int i=0;i<MAX;i++){
        items[i]=new Item;
      }
      
    }
    
    ~List (){
      
    }
    
    // добавить в конец
    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;
        while(index){
          i=items[i]->prev;
          index--;
        }
      }
      else{
        i=first;
        while(index){
          i=items[i]->next;
          index--;
        }
      }
      printf("found %i\n",i);
      return insert_after(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){
      //будем возвращать первый найденный индекс
      
      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){
      
      while(true){
        int i=findItem(value);
        
        if(i==NONE)
          break;
          
        removeItem(i);
      }
        
      
      
    }
    
    // удалить элемент с заданным индексом
    void removeAt(int index){
      int i=getItem(index);
      if(i!=NONE)
        removeItem(i);
      
    }
    
    
    
    void print_all(){
      int i=first;
      printf("\n\n  Count elements: %i \n", num);
      printf("  First index: %i \n",first);
      printf("  Last index: %i \n",last);
      printf("  index  |  prev  |  next  |  value  |  arr_key  \n");
      for(int j=0;j<num;j++){
        //if(i==NONE) break;
        printf("  %4i   |  %3i   |  %3i   |  %3i  |   %3i \n",i,items[i]->prev,items[i]->next, items[i]->value, i);
        i=items[i]->next;
      }
      
    }
    
    


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


};

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->insert(0,1);
  list->print_all();

    list->insert(1,2);
    list->insert(1,3);
    list->insert(1,4);
    list->insert(1,5);

    
  list->print_all();



    //assert(list->contains(1));
    //assert(!list->contains(568));

}


int main(){
  test();
  int i;
  scanf("%i",&i);
  return 0;
}