#include <array>
#include <cstdio>
#include <cstdint>
#include <cassert>
#include <algorithm>
int
main()
{
    std::array<int64_t,4> sample = {0,1,2,3};
    // use binary search to find >=1 left->right ascending order
    auto i0 = std::lower_bound(sample.begin(), sample.end(), 1);
    // use binary search to find <=2 right->left descending order
    // (reversal is because there is no inverse of lower_bound)
    auto i1 = std::lower_bound(sample.rbegin(), sample.rend(), 2, std::greater<int64_t>());
    printf("1 found at location %ld\n", i0 - sample.begin());
    // output: 1 found at location 1
    // end position minus distance from end:
    printf("2 found at location %ld\n", (sample.size()-1) - (i1 - sample.rbegin()) );
    // output: 2 found at location 2
// -------
printf("-------\n");
    // problem statement:
    // Given the two parallel arrays (nuts,seq) below, search for (1,1) and (2,0) indices
    // as above.  Hopefully using std::lower_bound, and hopefully without copying or
    // pre-combining the arrays.  Also check searching for (1,2), etc, and make sure we get the index
    // of (2,0) which is the first >= for the pair. Goal is to capture the range that includes
    // the ordered tuples ((first,last),(first,last)) whether or not the given tuples exist
    // in the data.
    std::array<int64_t,8> nuts = {0,0,1,1,2,2,3,3}; // always increasing
    std::array<uint64_t,8> seq = {0,1,0,1,0,1,0,1}; // always increasing within nuts value
// attempt:
    assert(seq.size()==nuts.size());
// <queries>
    //struct {int64_t first=1; uint64_t last=1;} first;
    //struct {int64_t first=2; uint64_t last=0;} last;
    
    //struct {int64_t first=1; uint64_t last=2;} first;
    //struct {int64_t first=1; uint64_t last=2;} last;
    //struct {int64_t first=4; uint64_t last=0;} first;
    //struct {int64_t first=4; uint64_t last=0;} last;
    struct {int64_t first=0; uint64_t last=1;} first;
    struct {int64_t first=2; uint64_t last=2;} last;
// </queries>
    // nuts:
    auto i2 = std::lower_bound(nuts.begin(), nuts.end(), first.first);
    auto u2 = std::upper_bound(nuts.begin(), nuts.end(), first.first);
    auto l2 = i2 - nuts.begin();
    auto ul2 = u2 - nuts.begin();
    auto i3 = std::lower_bound(nuts.rbegin(), nuts.rend(), last.first, std::greater<int64_t>());
    auto u3 = std::upper_bound(nuts.rbegin(), nuts.rend(), last.first, std::greater<int64_t>());
    auto l3 = i3 - nuts.rbegin(); // distance from end
    auto ul3 = u3 - nuts.rbegin();
    auto a3 = (nuts.size()-1) - l3;
    if(l2 > a3)
    {
        printf("nothing in nuts range found (%ld>%ld)\n",l2,a3);
        return 0;
    }
    printf("%ld found at location %ld\n", first.first, l2);
    printf("%ld found at location %ld\n", last.first, a3);
    // now narrow it for seq:
    auto i4 = std::lower_bound(seq.begin()+l2, seq.begin()+ul2, first.last);
    auto l4 = i4 - seq.begin();
    auto i5 = std::lower_bound(seq.rbegin()+l3, seq.rbegin()+ul3, last.last, std::greater<uint64_t>());
    auto l5 = i5 - seq.rbegin();
    auto a5 = (seq.size()-1) - l5;
    if(l4 > a5)
    {
        printf("nothing in seq range found\n");
        return 0;
    }
    printf("(%ld,%lu) found at location %ld\n", first.first, first.last, l4);
    printf("(%ld,%lu) found at location %ld\n", last.first, last.last, a5);
    return 0;
}