// ninja-fast factorial function with caching
Math.factorial = (function() {
	var cache = [1];
	return function(n) {
		return cache[n] ? cache[n] : cache[n] = n * Math.factorial(n - 1);
	}
})();

function num_sort(a, b) {
	return a - b;
}

var lcModel = {
	inflections: [],
	a: [],
	getMin: function(num) {
		if (!num) num = this.getCount();
		var r = 0;
		for(var i = 0; i < num; i++) {
			var elt = this.a[i];
			r += elt[0];
		}
		return r;
	},
	getMax: function(num) {
		if (!num) num = this.getCount();
		var r = 0;
		for(var i = 0; i < num; i++) {
			var elt = this.a[i];
			r += elt[1];
		}
		return r;
	},
	getMul: function(num) {
		if (!num) num = this.getCount();
		var r = 1;
		for(var i = 0; i < num; i++) {
			var elt = this.a[i];
			r *= (elt[1] - elt[0]);
		}
		return r;
	},
	getCount: function() {
		return this.a.length;
	},
	update: function(idx, lo, hi) { // 0-based index
		if ((this.a[idx][0] != lo)
		|| (this.a[idx][1] != hi)) {
			this.a[idx] = [lo, hi];
			this.reinflect(idx+1);
		}
	},
	add: function(lo, hi) {
		this.a.push([lo, hi]);
		// reinflect is unneccessary here
	},
	del: function(idx) { // 0-based index
		this.a.splice(idx, 1);
		this.reinflect();
		for (var i = idx, l = this.getCount(); i < l; i++) {
			this.reinflect(i+1);
		}
	},
	swap: function(idx) {
		var tmp = this.a[idx];
		this.a[idx] = this.a[idx+1];
		this.a[idx+1] = tmp;
		this._reinflect(idx + 1);
		this._reinflect(idx + 2);
	},
	clear: function() {
		this.a = [];
		this.inflections = [];
	},
	reinflect: function(num) { // 1-based index
		if (!num) num = this.getCount();
		for (var i = num; i <= this.getCount(); i++) {
			this._reinflect(i);
		}
	},
	_reinflect: function(num) { // 1-based index
		var b2 = 1 << num;
		this.inflections[num - 1] = [];
		var infl = this.inflections[num - 1];
		for (var mask = 0; mask < b2; mask++) {
			var sum = 0, count = 0, elt;
			for (var i = 0; i < num; i++) {
				if (mask & (1 << i)) {
					elt = this.a[i];
					sum += elt[1] - elt[0];
					count++;
				}
			}
			var sign = 1 - 2 * (count % 2);
			var point = infl.findBy({'value': sum});
			if (point) {
				point.sign += sign;
			} else {
				infl.push({'value': sum, 'sign': sign});
			}	
		}
		infl.sortBy('value');
	},
	probability: function(threshold) {
		var a = [];
		var p = 0, new_p = 0;
		for (var i = 0, l = this.getCount(); i < l; i++) {
			new_p = this.prob(threshold, i+1);
			a.push(new_p - p);
//			p = new_p;
		}
		return a;
	},
	prob: function(threshold, num) {
		var infl = this.inflections[num-1];
		var min = this.getMin(num);
		var max = this.getMax(num);
		var V = this.getMul(num);
		if (threshold > max) return 0;
		if (threshold < min) return 1;
		threshold -= min;
		var i = 0, sum = 0, elt;
		while ((elt = infl[i++]) && (elt.value < threshold)) {
			sum += elt.sign * Math.pow(threshold - elt.value, num);
		}
		return (V - sum / Math.factorial(num)) / V;
	},
	cycled: function(threshold) {
		return [
			Math.ceil(threshold / lcModel.getMax()),
			Math.ceil(threshold / lcModel.getMin())
		];
	}
}