static <T extends Comparable<T>> void qsImpl(List<T>list) {
		if (list.size()<=1) return;
		T pivot= mmImpl(list, list.size()/2);
		int p=-1,l=1;
		for (int i=0;i<list.size()&&p==-1;++i) if (list.get(i).compareTo(pivot)==0)p=i;
		Collections.swap(list, 0, p);
		for (int i=1;i<list.size();++i) if(list.get(i).compareTo(pivot)<=0) Collections.swap(list, i, l++);
		Collections.swap(list, 0, l-1);
		qsImpl(list.subList(0, l-1));
		qsImpl(list.subList(l, list.size()));
	}