using System;

namespace TestCodility2
{
    class Program
    {
        public static int solutionBetter(int[] A, int X)
        {
            int N = A.Length;
            if (N == 0)
            {
                return (-1);
            }
            int l = 0;
            int r = N - 1;
            while (l < r)
            {
                int m = (l + r) / 2;

                var delta = A[m] - X;

                if (delta == 0)
                {
                    return m;
                }
                else if (delta > 0)
                {
                    r = m - 1;
                }
                else
                {
                    l = m + 1;
                }
            }
            return -1;
        }

        public static int solution(int[] A, int X)
        {
            int N = A.Length;
            if (N == 0)
            {
                return (-1);
            }
            int l = 0;
            int r = N - 1;
            while (l < r)
            {
                int m = (l + r) / 2;

                if (A[m] > X)
                {
                    r = m - 1;
                }
                else if (l < m)
                {
                    l = m;
                }
                else if (A[l] == X)
                {
                    r = l;
                }
                else
                {
                    l = r;
                }
            }
            if (A[l] == X)
            {
                return l;
            }
            return -1;
        }

        static void CheckSolution(int[] A, int X, int expected)
        {
            var result = solution(A, X);
            if (result != expected)
            {
                var msg = $"{expected} != {result}";
                Console.WriteLine(msg);
                throw new Exception(msg);
            }
        }

        static void CheckSolution(int[] A, int X, int expectedMin, int expectedMax)
        {
            var result = solution(A, X);
            //var result = solutionBetter(A, X);
            if (result < expectedMin || result > expectedMax)
            {
                var msg = $"{result} != [{expectedMin}...{expectedMax}]";
                Console.WriteLine(msg);
                throw new Exception(msg);
            }
        }

        static void Main(string[] args)
        {
            CheckSolution(new[] { 1, 2, 5, 9, 9 }, 5, 2);
            CheckSolution(new[] { 1, 2, 5, 9, 9 }, 10, -1);
            CheckSolution(new[] { -9, -3, -1 }, -1, 2);
            CheckSolution(new[] { -9, -3, -1 }, -9, 0);
            CheckSolution(new[] { -9, -3, -1 }, -3, 1);
            CheckSolution(new[] { -9, -3, -3, -3, -3, -1 }, -3, 1, 4);
            CheckSolution(new[] { -9, -9, -9, -9, -3, -3, -3, -3, -1 }, -3, 4, 7);
            CheckSolution(new[] { -9, -3, -3, -3, -3, -2, -1 }, -2, 5);
            CheckSolution(new[] { -9, -3, 0, 2, 5 }, -500, -1);
            CheckSolution(new[] { 0 }, -500, -1);
            CheckSolution(new[] { 0 }, 0, 0);
            CheckSolution(new int[0], 0, -1);
        }
    }
}