#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
 
 
using namespace std;
 
struct Point{
	int x;
	int y;
};
 
struct compare_functor : public binary_function<bool,Point,Point>
{
	bool operator ()(const Point &lhs, const Point &rhs) {
		return lhs.x<rhs.x ;
	}
};
 
int main() {
	vector<Point> points;
	for (int i = 0; i<100; i++) {
		//ランダムな点を生成
		Point pt = { rand() % (i+1), 0 };
		auto pos=lower_bound(points.begin(),points.end(),pt,compare_functor()) ;
		if(pos==points.end())
		  points.push_back(pt) ;
		else
		  points.insert(pos,pt) ;
	}
 
	//要素を順に表示
	for (int i = 0; i < 100; i++) {
		cout << points[i].x << endl;
	}
 
	return 0;
 
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IFBvaW50ewoJaW50IHg7CglpbnQgeTsKfTsKCnN0cnVjdCBjb21wYXJlX2Z1bmN0b3IgOiBwdWJsaWMgYmluYXJ5X2Z1bmN0aW9uPGJvb2wsUG9pbnQsUG9pbnQ+CnsKCWJvb2wgb3BlcmF0b3IgKCkoY29uc3QgUG9pbnQgJmxocywgY29uc3QgUG9pbnQgJnJocykgewoJCXJldHVybiBsaHMueDxyaHMueCA7Cgl9Cn07CgppbnQgbWFpbigpIHsKCXZlY3RvcjxQb2ludD4gcG9pbnRzOwoJZm9yIChpbnQgaSA9IDA7IGk8MTAwOyBpKyspIHsKCQkvL+ODqeODs+ODgOODoOOBqueCueOCkueUn+aIkAoJCVBvaW50IHB0ID0geyByYW5kKCkgJSAoaSsxKSwgMCB9OwoJCWF1dG8gcG9zPWxvd2VyX2JvdW5kKHBvaW50cy5iZWdpbigpLHBvaW50cy5lbmQoKSxwdCxjb21wYXJlX2Z1bmN0b3IoKSkgOwoJCWlmKHBvcz09cG9pbnRzLmVuZCgpKQoJCSAgcG9pbnRzLnB1c2hfYmFjayhwdCkgOwoJCWVsc2UKCQkgIHBvaW50cy5pbnNlcnQocG9zLHB0KSA7Cgl9CgoJLy/opoHntKDjgpLpoIbjgavooajnpLoKCWZvciAoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspIHsKCQljb3V0IDw8IHBvaW50c1tpXS54IDw8IGVuZGw7Cgl9CgoJcmV0dXJuIDA7Cgp9