#include <vector>
#include <algorithm>
#include <iostream>
 
template <typename iter>
void sort_b(iter first, iter last)
{
	while(first != last)
	{
		iter current = first;
		while(2 <= last - current)
		{
			if(*current > *(current + 1)) std::iter_swap(current, current + 1);
			++current;
		}
		--last;
	}
}
 
int main()
{
	std::vector<int> v { 1, 2, 3, 9, 8, 7, 6, 5, 4 };
 
	std::cout << "input: ";
	std::for_each(v.begin(), v.end(), [](int i){
		std::cout << i << " ";
	});
	std::cout << std::endl;
 
	sort_b(v.begin(), v.end());
 
	std::cout << "output: ";
	std::for_each(v.begin(), v.end(), [](int i){
		std::cout << i << " ";
	});
 
	return 0;
}

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdGVtcGxhdGUgPHR5cGVuYW1lIGl0ZXI+CnZvaWQgc29ydF9iKGl0ZXIgZmlyc3QsIGl0ZXIgbGFzdCkKewoJd2hpbGUoZmlyc3QgIT0gbGFzdCkKCXsKCQlpdGVyIGN1cnJlbnQgPSBmaXJzdDsKCQl3aGlsZSgyIDw9IGxhc3QgLSBjdXJyZW50KQoJCXsKCQkJaWYoKmN1cnJlbnQgPiAqKGN1cnJlbnQgKyAxKSkgc3RkOjppdGVyX3N3YXAoY3VycmVudCwgY3VycmVudCArIDEpOwoJCQkrK2N1cnJlbnQ7CgkJfQoJCS0tbGFzdDsKCX0KfQoKaW50IG1haW4oKQp7CglzdGQ6OnZlY3RvcjxpbnQ+IHYgeyAxLCAyLCAzLCA5LCA4LCA3LCA2LCA1LCA0IH07CgkKCXN0ZDo6Y291dCA8PCAiaW5wdXQ6ICI7CglzdGQ6OmZvcl9lYWNoKHYuYmVnaW4oKSwgdi5lbmQoKSwgW10oaW50IGkpewoJCXN0ZDo6Y291dCA8PCBpIDw8ICIgIjsKCX0pOwoJc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCQoJc29ydF9iKHYuYmVnaW4oKSwgdi5lbmQoKSk7CgkKCXN0ZDo6Y291dCA8PCAib3V0cHV0OiAiOwoJc3RkOjpmb3JfZWFjaCh2LmJlZ2luKCksIHYuZW5kKCksIFtdKGludCBpKXsKCQlzdGQ6OmNvdXQgPDwgaSA8PCAiICI7Cgl9KTsKCQoJcmV0dXJuIDA7Cn0=