#pragma once

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <list>

template<typename T, typename Iterator>
Iterator FindImpl(const T& value, Iterator first, Iterator last, std::random_access_iterator_tag){
    int l = 0, r = last - first - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (*(first + m) < value) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if (first + l < last && *(first + l) == value) {
        return first + l;
    }
    return last;
}

template<typename T, typename Iterator>
Iterator FindImpl(const T& value, Iterator first, Iterator last, std::bidirectional_iterator_tag){
    Iterator it = first;
    T v = value;
    while (it != last && *it < v)
        it++;
    if (it != last && *it == value) {
        return it;
    }
    return last;
}

template<typename T, typename Iterator>
Iterator Find(const T& value, Iterator first, Iterator last){
    typedef typename std::iterator_traits<Iterator>::iterator_category category;
    return FindImpl(value, first, last, category());
}