#include <iostream>
#include <vector>

template <typename InputIt, typename OutputIt>
void ComputeMinUntilHere(InputIt begin, InputIt end, OutputIt output)
{
    if (begin == end) {
        return;
    }
    auto min = *begin;
    while (begin != end) {
        min = std::min(min, *begin);
        *output = min;
        ++begin;
        ++output;
    }
}

struct MinByBlock
{
    std::vector<int> minUntilHere;
    std::vector<int> minStartingHere;
};

MinByBlock ComputeMinByBlock(const std::vector<int>&v, std::size_t blockSize)
{
    MinByBlock res;
    res.minUntilHere.resize(v.size());
    res.minStartingHere.resize(v.size());
    for (std::size_t i = 0; i < v.size(); i += blockSize) {
        const auto blockBegin = v.begin() + i;
        const auto blockEndIndex = std::min(i + blockSize, v.size());
        const auto blockEnd = v.begin() + blockEndIndex;
        
        ComputeMinUntilHere(blockBegin, blockEnd, res.minUntilHere.begin() + i);
        ComputeMinUntilHere(std::make_reverse_iterator(blockEnd),
                            std::make_reverse_iterator(blockBegin),
                            std::make_reverse_iterator(res.minStartingHere.begin() + blockEndIndex));
    }
    return res;
}

void print(const std::vector<int>& v)
{
    std::cout << "{ ";
    for (const auto e : v) {
        std::cout << e << " "; 
    }
    std::cout << "}\n";
}

int main()
{
    const std::vector<int> v = {2, 1, 3, 6, 5, 4, 42};
    
    const auto res = ComputeMinByBlock(v, 2);
    
    print(res.minUntilHere);
    print(res.minStartingHere);
    
}