#include <iostream>
#include<stack>
#include<vector>
using namespace std;

// To execute C++, please define "int main()"
int main() {
  
}

/**
/**
 * At LinkedIn we use JSON/YAML/HOCON configuration files in many different places to configure our services and applications
 * (for example what security keys should we use to configure connections to the database?)
 *
 * Therefore we have configuration validators that validate that when you change the configuration ... it would correctly compile and it is correctly formed (or you can quite literally take down multiple services).
 *
 * This function determines if the parenthesis '(' and ')' in a string are properly matched.
 * and it ignores non-brace characters.
 *
 * Input: [A-Za-z0-9].* String
 * Output: Boolean
 *
 * Some examples:
 * "()()()()"   -> true
 * "((45+)*a3)" -> true
 * "(((())())"  -> false
 * "))((" -> false  
 */
 
  bool matched(string s) {
    // Implementation here
    stack<char>st;
    int openP = 0;
    //int closeP = 0;
    for(char c: s){
      if(c == '(') {
        openP++;
      }else if(c == ')') {       
        if(openP == 0) return false;
        openP--;
        st.pop(); /* the st.pop() here is the residue of my Brute-force approach. I was going to remove it but the interviewer said it's ok.*/
      }
    }

    return openP == 0 ? true : false;

    //return false;

  }

// Given a sorted array (e.g. 1 2 3 4 5 6 7). that has been transposed (that is, some of the numbers have been removed from one end and attached to the other, e.g.  6 7 1 2 3 4 5), write a function to determine if a given number is present in the array.
//
// (it's the same as rotating the array - consider writing the numbers down and then taking some of the end and adding it to the front
// e.g. we can do 1 2 3 4 and take the 3 4 and move it to the front to give 3 4 1 2 
// For example, here's a transposed array: 6 7 1 2 3 4 5. Note: numbers don't have to be ascending (because we shift the previously sorted array).
// Task #1: Find number "1". Should return true.
// Task #2: Find number "4". Should return true.
/*
6 7 1 2 3 4 5
pass 1:
low =0 
high 7

mid = 3 

pass 2:
low = 0
high = 3
mid = 1

pass 3:
low = 2
high = 2
mid = 2

6 7
pass 1:
low =0
high = 2
mid = 1

3 1 2
pass 1:
low = 0
high = 3
mid  = 1

*/
bool isInList(int targetValue, vector<int>& arr) {

  int low = 0, high = arr.size() - 1; /* During my initial implementation, I kept high = arr.size(), when the interviewer pointed out invalid index, I quickly corrected this.*/
  while(low <= high) {
    int mid = low + (high - low)/2;

    if(arr[mid] == targetValue) return true;

    if(arr[low] < arr[mid]) {
       if(targetValue < arr[mid] && targetValue >= arr[low]) {
        high = mid - 1;
       }else  {
       low = mid + 1;
       }
    }else {
           if(targetValue > arr[mid] && targetValue <= arr[high]) {
            low = mid + 1;
           }else
           high = mid - 1;
    }
  }

  return false;
}