#include <iostream>
using namespace std;
 
int main() {
	// your code goes here
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglyZXR1cm4gMDsKfQ==

CgpjbGFzcyBhcnJheXsKcHJpdmF0ZToKICAgIGludCBzaXplOwogICAgaW50IGxlbmd0aDsKICAgIGludCppdGVtczsKcHVibGljOgogICAgYXJyYXkoaW50IGFycnNpemUpCgp7CiAgICBzaXplID1hcnJzaXplOwogICAgbGVuZ3RoID0wOwogICAgaXRlbXMgPW5ldyBpbnRbYXJyc2l6ZV07Cn0Kdm9pZCBmaWxsKCkKewogICAgaW50IG51X29mX2l0ZW1zOwogICAgY291dCZsdDsmbHQ7JnF1b3Q7SG93IG1hbnkgaXRlbXMgeW91IHdhbnQgdG8gZmlsbCAmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICBjaW4mZ3Q7Jmd0O251X29mX2l0ZW1zOwogICAgaWYobnVfb2ZfaXRlbXMmZ3Q7c2l6ZSkKICAgIHsKICAgICAgICBjb3V0Jmx0OyZsdDsmcXVvdDtZb3UgY2Fubm90IGV4Y2VlZCB0aGUgYXJyYXkgc2l6ZSZxdW90OyZsdDsmbHQ7ZW5kbDsKICAgICAgICByZXR1cm47CgogICAgfQogICAgZWxzZXsKICAgICAgICBmb3IoaW50IGk9MDtpJmx0O251X29mX2l0ZW1zO2krKyl7CiAgICAgICAgICAgIGNvdXQgJmx0OyZsdDsmcXVvdDtFbnRlciBpdGVtIG9uICZxdW90OyZsdDsmbHQ7aSZsdDsmbHQ7ZW5kbDsKICAgICAgICAgICAgY2luICZndDsmZ3Q7aXRlbXNbaV07CiAgICAgICAgICAgIGxlbmd0aCsrOwogICAgICAgIH0KICAgIH0KfQp2b2lkIERpc3BsYXkoKQp7CiAgICBjb3V0Jmx0OyZsdDsmcXVvdDtEaXNwbGF5IEFycmF5IGNvbnRlbnQmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICBmb3IoaW50IGk9MDtpJmx0O2xlbmd0aDtpKyspCgogICAgewogICAgICAgIGNvdXQmbHQ7Jmx0O2l0ZW1zW2ldJmx0OyZsdDtlbmRsOwogICAgfQoKfQppbnQgZ2V0U2l6ZSgpCnsKICAgIHJldHVybiBzaXplOwp9CmludCBnZXRMZW5ndGgoKQp7CiAgICByZXR1cm4gbGVuZ3RoOwp9CmludCBzZWFyY2goaW50IGtleSkKewogICAgaW50IGluZGV4PS0xOwogICAgZm9yKGludCBpPTA7aSZsdDtsZW5ndGg7aSsrKQogICAgewogICAgICAgaWYoaXRlbXNbaV09PWtleSkKICAgICAgIHsKICAgICAgICAgICBpbmRleD1pOwogICAgICAgICAgIGJyZWFrOwogICAgICAgfQogICAgfQogICAgICAgcmV0dXJuIGluZGV4OwoKICAgIH0Kdm9pZCBBcHBlbmQoaW50IG5ld0l0ZW0pCgp7CiAgaWYobGVuZ3RoJmx0O3NpemUpCiAgewogICAgICBpdGVtc1tsZW5ndGhdPW5ld0l0ZW07CiAgICAgIGxlbmd0aCsrOwogIH1lbHNlCiAgewogICAgICBjb3V0Jmx0OyZsdDsmcXVvdDtBcnJheSBpcyBmaWxsJnF1b3Q7Jmx0OyZsdDtlbmRsOwogIH0KfQp2b2lkIGluc2VydChpbnQgaW5kZXgsaW50IG5ld0l0ZW0pCnsKICAgIGlmKGluZGV4ICZndDs9MCZhbXA7JmFtcDsgaW5kZXggJmx0O3NpemUpCiAgICB7CiAgICAgICAgZm9yKGludCBpPWxlbmd0aDtpJmd0O2luZGV4O2ktLSkKICAgICAgICB7CiAgICAgICAgICAgaXRlbXNbaV09aXRlbXNbaS0xXTsKICAgICAgICB9CiAgICAgICAgaXRlbXNbaW5kZXhdPW5ld0l0ZW07CiAgICAgICAgbGVuZ3RoKys7CiAgICB9CiAgICBlbHNlewogICAgICAgIGNvdXQmbHQ7Jmx0OyZxdW90O0VudGVyIC1pbmRleCBvdXQgb2YgUmFuZ2UmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICB9Cn0Kdm9pZCBEZWxldGUoaW50IGluZGV4KQp7CiAgICBpZihpbmRleCAmZ3Q7PTAgJmFtcDsmYW1wOyBpbmRleCAmbHQ7IHNpemUpCiAgICB7CiAgICAgICAgZm9yKGludCBpPWluZGV4O2kmbHQ7IGxlbmd0aCAtMTtpKyspCiAgICAgICAgewogICAgICAgICAgIGl0ZW1zW2ldPWl0ZW1zW2krMV07CiAgICAgICAgICAgbGVuZ3RoLS07CiAgICAgICAgfQoKCiAgICB9ZWxzZXsKICAgIGNvdXQgJmx0OyZsdDsmcXVvdDtpbmRleCBvdXQgb2YgUmFuZ2UmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICB9CiAgICB9Cgp9OwoKCmludCBtYWluKCkKewogICAgY291dCZsdDsmbHQ7JnF1b3Q7SGVsbG8gVGhpcyBpcyBBcnJheSBBRFQgZGVtbyZxdW90OyZsdDsmbHQ7ZW5kbDsKICAgIGludCBhcnJheXNpemU7CiAgICBjb3V0Jmx0OyZsdDsmcXVvdDtFbnRlciB0aGUgQXJyYXkgU2l6ZSAmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICBjaW4mZ3Q7Jmd0O2FycmF5c2l6ZTsKICAgIGFycmF5IG15YXJyYXkoYXJyYXlzaXplKTsKICAgIG15YXJyYXkuZmlsbCgpOwogICAgY291dCZsdDsmbHQ7JnF1b3Q7QXJyYXkgc2l6ZSA9ICZxdW90OyAmbHQ7Jmx0OyBteWFycmF5LmdldFNpemUoKSAmbHQ7Jmx0O2VuZGw7CiAgICBjb3V0Jmx0OyZsdDsgJnF1b3Q7d2hpbGUgbGVuZ3RoID0gJnF1b3Q7ICZsdDsmbHQ7bXlhcnJheS5nZXRMZW5ndGgoKSAmbHQ7Jmx0O2VuZGw7CiAgICBteWFycmF5LkRpc3BsYXkoKTsKICAgIGNvdXQmbHQ7Jmx0OyZxdW90O0VudGVyIHRoZSB2YWx1ZSB0byBzZWFyY2ggZm9yJnF1b3Q7Jmx0OyZsdDtlbmRsOwogICAgaW50IGtleTsKICAgIGNpbiZndDsmZ3Q7a2V5OwogICAgIGludCBpbmRleCA9IG15YXJyYXkuc2VhcmNoKGtleSk7CiAgICBpZihpbmRleCA9PSAtMSl7CiAgICAgICAgY291dCZsdDsmbHQ7JnF1b3Q7SXRlbSBub3QgZm91bmQmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICB9CiAgICBlbHNlewogICAgICAgIGNvdXQmbHQ7Jmx0OyZxdW90O0l0ZW0gZm91bmQgQCBwb3NpdGlvbiAmcXVvdDsmbHQ7Jmx0O2luZGV4Jmx0OyZsdDtlbmRsOwogICAgICAgIH0KICAgICAgICBpbnQgbmV3SXRlbTsKICAgICAgICBjb3V0Jmx0OyZsdDsmcXVvdDtFbnRlciBuZXdJdGVtIHRvIGFkZCB0byB0aGUgYXJyYXkmcXVvdDsmbHQ7Jmx0O2VuZGw7CiAgICAgICAgY2luJmd0OyZndDtuZXdJdGVtOwogICAgICAgIG15YXJyYXkuQXBwZW5kKG5ld0l0ZW0pOwogICAgICAgIG15YXJyYXkuRGlzcGxheSgpOwogICAgICAgIGNvdXQmbHQ7Jmx0OyZxdW90O0VudGVyIGluZGV4IGFuZCBpdGVtJnF1b3Q7Jmx0OyZsdDtlbmRsOwogICAgICAgIGNpbiZndDsmZ3Q7aW5kZXg7CiAgICAgICAgY2luJmd0OyZndDtuZXdJdGVtOwogICAgICAgIG15YXJyYXkuaW5zZXJ0KGluZGV4LG5ld0l0ZW0pOwogICAgICAgIG15YXJyYXkuRGlzcGxheSgpOwogICAgICAgICAgICBjb3V0Jmx0OyZsdDsmcXVvdDtBcnJheSBzaXplID0gJnF1b3Q7ICZsdDsmbHQ7IG15YXJyYXkuZ2V0U2l6ZSgpICZsdDsmbHQ7ZW5kbDsKICAgIGNvdXQmbHQ7Jmx0OyAmcXVvdDt3aGlsZSBsZW5ndGggPSAmcXVvdDsgJmx0OyZsdDtteWFycmF5LmdldExlbmd0aCgpICZsdDsmbHQ7ZW5kbDsKCiAgICBjb3V0ICZsdDsmbHQ7JnF1b3Q7RW50ZXIgaW5kZXggdG8gZGVsZXRlIGl0cyBpdGVtJnF1b3Q7Jmx0OyZsdDtlbmRsOwogICAgY2luJmd0OyZndDtpbmRleDsKICAgIG15YXJyYXkuRGVsZXRlKGluZGV4KTsKICAgIG15YXJyYXkuRGlzcGxheSgpOwogICAgY291dCZsdDsmbHQ7JnF1b3Q7QXJyYXkgc2l6ZSA9ICZxdW90OyAmbHQ7Jmx0OyBteWFycmF5LmdldFNpemUoKSAmbHQ7Jmx0O2VuZGw7CiAgICBjb3V0Jmx0OyZsdDsgJnF1b3Q7d2hpbGUgbGVuZ3RoID0gJnF1b3Q7ICZsdDsmbHQ7bXlhcnJheS5nZXRMZW5ndGgoKSAmbHQ7Jmx0O2VuZGw7CgpyZXR1cm4gMDsKCn0=

class array{
private:
    int size;
    int length;
    int*items;
public:
    array(int arrsize)

{
    size =arrsize;
    length =0;
    items =new int[arrsize];
}
void fill()
{
    int nu_of_items;
    cout<<"How many items you want to fill "<<endl;
    cin>>nu_of_items;
    if(nu_of_items>size)
    {
        cout<<"You cannot exceed the array size"<<endl;
        return;

    }
    else{
        for(int i=0;i<nu_of_items;i++){
            cout <<"Enter item on "<<i<<endl;
            cin >>items[i];
            length++;
        }
    }
}
void Display()
{
    cout<<"Display Array content"<<endl;
    for(int i=0;i<length;i++)

    {
        cout<<items[i]<<endl;
    }

}
int getSize()
{
    return size;
}
int getLength()
{
    return length;
}
int search(int key)
{
    int index=-1;
    for(int i=0;i<length;i++)
    {
       if(items[i]==key)
       {
           index=i;
           break;
       }
    }
       return index;

    }
void Append(int newItem)

{
  if(length<size)
  {
      items[length]=newItem;
      length++;
  }else
  {
      cout<<"Array is fill"<<endl;
  }
}
void insert(int index,int newItem)
{
    if(index >=0&& index <size)
    {
        for(int i=length;i>index;i--)
        {
           items[i]=items[i-1];
        }
        items[index]=newItem;
        length++;
    }
    else{
        cout<<"Enter -index out of Range"<<endl;
    }
}
void Delete(int index)
{
    if(index >=0 && index < size)
    {
        for(int i=index;i< length -1;i++)
        {
           items[i]=items[i+1];
           length--;
        }


    }else{
    cout <<"index out of Range"<<endl;
    }
    }

};


int main()
{
    cout<<"Hello This is Array ADT demo"<<endl;
    int arraysize;
    cout<<"Enter the Array Size "<<endl;
    cin>>arraysize;
    array myarray(arraysize);
    myarray.fill();
    cout<<"Array size = " << myarray.getSize() <<endl;
    cout<< "while length = " <<myarray.getLength() <<endl;
    myarray.Display();
    cout<<"Enter the value to search for"<<endl;
    int key;
    cin>>key;
     int index = myarray.search(key);
    if(index == -1){
        cout<<"Item not found"<<endl;
    }
    else{
        cout<<"Item found @ position "<<index<<endl;
        }
        int newItem;
        cout<<"Enter newItem to add to the array"<<endl;
        cin>>newItem;
        myarray.Append(newItem);
        myarray.Display();
        cout<<"Enter index and item"<<endl;
        cin>>index;
        cin>>newItem;
        myarray.insert(index,newItem);
        myarray.Display();
            cout<<"Array size = " << myarray.getSize() <<endl;
    cout<< "while length = " <<myarray.getLength() <<endl;

    cout <<"Enter index to delete its item"<<endl;
    cin>>index;
    myarray.Delete(index);
    myarray.Display();
    cout<<"Array size = " << myarray.getSize() <<endl;
    cout<< "while length = " <<myarray.getLength() <<endl;

return 0;

}