#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
 
 
using namespace std;
 
struct Point{
	int x;
	int y;
};
 
  template<class iterator,class T,class O>
  iterator insert_pos(iterator beg, iterator end,T val,O op) {
    while(beg!=end) {
      iterator mid = beg + (end-beg)/2 ;
      if(!op(*mid,val)) end = mid ;
      else if(beg==mid) return end ;
      else beg = mid ;
    }
    return end ;
  }
 
 
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=insert_pos(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;
 
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IFBvaW50ewoJaW50IHg7CglpbnQgeTsKfTsKCiAgdGVtcGxhdGU8Y2xhc3MgaXRlcmF0b3IsY2xhc3MgVCxjbGFzcyBPPgogIGl0ZXJhdG9yIGluc2VydF9wb3MoaXRlcmF0b3IgYmVnLCBpdGVyYXRvciBlbmQsVCB2YWwsTyBvcCkgewogICAgd2hpbGUoYmVnIT1lbmQpIHsKICAgICAgaXRlcmF0b3IgbWlkID0gYmVnICsgKGVuZC1iZWcpLzIgOwogICAgICBpZighb3AoKm1pZCx2YWwpKSBlbmQgPSBtaWQgOwogICAgICBlbHNlIGlmKGJlZz09bWlkKSByZXR1cm4gZW5kIDsKICAgICAgZWxzZSBiZWcgPSBtaWQgOwogICAgfQogICAgcmV0dXJuIGVuZCA7CiAgfQoKCnN0cnVjdCBjb21wYXJlX2Z1bmN0b3IgOiBwdWJsaWMgYmluYXJ5X2Z1bmN0aW9uPGJvb2wsUG9pbnQsUG9pbnQ+CnsKCWJvb2wgb3BlcmF0b3IgKCkoY29uc3QgUG9pbnQgJmxocywgY29uc3QgUG9pbnQgJnJocykgewoJCXJldHVybiBsaHMueDxyaHMueCA7Cgl9Cn07CgppbnQgbWFpbigpIHsKCXZlY3RvcjxQb2ludD4gcG9pbnRzOwoJZm9yIChpbnQgaSA9IDA7IGk8MTAwOyBpKyspIHsKCQkvL+ODqeODs+ODgOODoOOBqueCueOCkueUn+aIkAoJCVBvaW50IHB0ID0geyByYW5kKCkgJSAoaSsxKSwgMCB9OwoJCWF1dG8gcG9zPWluc2VydF9wb3MocG9pbnRzLmJlZ2luKCkscG9pbnRzLmVuZCgpLHB0LGNvbXBhcmVfZnVuY3RvcigpKSA7CgkJaWYocG9zPT1wb2ludHMuZW5kKCkpCgkJICBwb2ludHMucHVzaF9iYWNrKHB0KSA7CgkJZWxzZQoJCSAgcG9pbnRzLmluc2VydChwb3MscHQpIDsKCX0KCgkvL+imgee0oOOCkumghuOBq+ihqOekugoJZm9yIChpbnQgaSA9IDA7IGkgPCAxMDA7IGkrKykgewoJCWNvdXQgPDwgcG9pbnRzW2ldLnggPDwgZW5kbDsKCX0KCglyZXR1cm4gMDsKCn0=