static int select(int[] a, int l, int r, int k) {
		if (l == r)
			return a[l];
		int val = a[l], p = l, q = r;
		for (int i = l; i <= q;) {
			if (a[i] < val) {
				swap(a, p++, i++);
			} else if (a[i] > val) {
				swap(a, q--, i);
			} else {
				i++;
			}
		}
		if (p <= k + l && q >= k + l) return val;
		else if (k + l < p)
			return select(a, l, p, k);
		else
			return select(a, q, r, k - (p-l+1));
	}