#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int Binarysearch_(int M[], int n, int k, int flag)
{
    int left = 0;
    int right = n-1;
    int mid;

    int result = -1;
    while(left<=right)
    {
        mid = (left+right)/2;
        if (k==M[mid])
        {
            result = mid;
            if (flag == 1) right= mid-1;
            if (flag == 2) left = mid +1;
        }
        else if (k<M[mid]) right = mid - 1;
        else left = mid+1;
    }
    return result;

}

int main()
{
    int A[] = {1,1,1,3,3,3,3,3,3,3,5,6,6,8,9,9};

    int n = sizeof(A)/sizeof(A[0]);
    // 1 == firstOccurance
    // 2 == LastOccurance
    int firstOccurance = Binarysearch_(A,n,3,1);
    int lastOccurance = Binarysearch_(A,n,3,2);

    if(firstOccurance==-1)
    {
        cout << "the element is not in the array";
    }else
    {
        cout << "the element appears "<<lastOccurance-firstOccurance + 1;
    }
    return 0;
}