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

template <typename T>
using ptr = T*;

int lengthOfLIS(std::vector<int>& nums)
{
	auto ps = vector<stack<int>>();
	for (auto const& n : nums) {
		auto pn = stack<int>();
		pn.push(n);
		auto stack = ranges::lower_bound(ps, pn, [](auto const& s1, auto const& s2){ return s1.top() < s2.top(); });
		if (stack != ps.end()) {
			stack->push(n);
		} else {
			ps.push_back(pn);
		}
	}
	return ps.size();
}

auto main() -> int
{
	auto nums1 = std::vector{10,9,2,5,3,7,101,18};
	auto nums2 = std::vector{0,1,0,3,2,3};
	auto nums3 = std::vector{7,7,7,7,7,7,7};
	auto nums4 = std::vector{ 1, 10, 2, 3, 4, 5 };
	auto nums5 = std::vector{ 1, 10, 2, 3, 4, 20, 5 };
	auto nums6 = std::vector{ 1, 0 };

	std::cout << std::format("nums1: {}\n", lengthOfLIS(nums1));
	std::cout << std::format("nums2: {}\n", lengthOfLIS(nums2));
	std::cout << std::format("nums3: {}\n", lengthOfLIS(nums3));
	std::cout << std::format("nums4: {}\n", lengthOfLIS(nums4));
	std::cout << std::format("nums5: {}\n", lengthOfLIS(nums5));
	std::cout << std::format("nums6: {}\n", lengthOfLIS(nums6));
	return 0;
}