#include <bits/stdc++.h>
using namespace std;
void insertionSort(string ar[],int n)
{
    string key;
    int j=0;
    for(int i=1;i<n;i++){
        key=ar[i];
        j=i-1;
        while(j>=0 && ar[j]>key){
            ar[j+1]=ar[j];
            j=j-1;
        }
        ar[j+1]=key;
    }
}

int search(string ar[],int n,string e)
{
     int f,l,m;
    f=0;
    l=n-1;

    while(f<=l){
        m=(f+l)/2;
        if(e==ar[m])
            return(m);
        else
            if(e>ar[m])
                f=m+1;
            else
                l=m-1;
    }

    return -1;


}
int main()
{
    int n;
    cout<<"Enter string number: ";

    cin>>n;
    string ar[n];
    for(int i=0;i<n;i++){
        cin>>ar[i];
    }
    insertionSort(ar,n);
    cout<<"After sorting: "<<endl;
    for(int i=0;i<n;i++){
        cout<<ar[i]<<endl;
    }
    cout<<"How many data you want to search: "<<endl;
    int z;
    cin>>z;
    string e;
    for(int i=0;i<z;i++){
        cout<<"Case: "<<i+1<<endl;
        cout<<"\nEnter Data You want to search: ";
        cin>>e;
        int ans;
        ans=search(ar,n,e);

        if(ans!=-1)
            cout<<e<<" is found at Index = "<<ans<<endl;
        else
            cout<<e<<" is not found in the Array";
    }



}