using System;

public class Program

{

    public static void Main()

    {

        int[] arr = new int[] {1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7, 8};

        int query = 4;

        Console.WriteLine(Find(arr, query));

        Console.WriteLine(FindLeft(arr, query));

        Console.WriteLine(FindRight(arr, query));

    }

    public delegate string Condition(int mid);

    public static int GenericBinarySearch(int lo, int hi, Condition cond)

    {

        while(lo<=hi)

        { 

            int mid = (lo+hi)/2;

            string result = cond(mid);

            if(result=="found") return mid;

            else if(result=="left") hi = mid-1;

            else lo=mid+1;

        }

        return -1;

    }

    public static int Find(int[] arr, int query)

    {

        int lo = 0;

        int hi = arr.Length-1;

        string CondLeft(int mid)

        {

            if(arr[mid]==query)

            {

                return "found";

            }

            else if(arr[mid]>query) 

            {

                return "left";

            }

            else return "right";

        }

        return GenericBinarySearch(lo, hi, CondLeft);

    }

    public static int FindLeft(int[] arr, int query)

    {

        int lo = 0;

        int hi = arr.Length-1;

        string CondLeft(int mid)

        {

            if(arr[mid]==query)

            {

                if(mid-1>0 && arr[mid-1]==query) return "left";

                return "found";

            }

            else if(arr[mid]>query) 

            {

                return "left";

            }

            else return "right";

        }

        return GenericBinarySearch(lo, hi, CondLeft);

    }

    public static int FindRight(int[] arr, int query)

    {

        int lo = 0;

        int hi = arr.Length-1;

        string CondLeft(int mid)

        {

            if(arr[mid]==query)

            {

                if(mid+1<arr.Length && arr[mid+1]==query) return "right";

                return "found";

            }

            else if(arr[mid]>query) 

            {

                return "left";

            }

            else return "right";

        }

        return GenericBinarySearch(lo, hi, CondLeft);

    }

}