NRP

int bsearch(int arr[], vector<int> &T, int l, int r, int key) {
	while (r - l > 1) {
		int m = l + (r - l)/2;
		if (arr[T[m]] >= key)
			r = m;
		else
			l = m;
	}
	return r;
}

int NRP(int arr[], int n) {
	vector<int> tail(n, 0);
	vector<int> prev(n, -1);

	int len = 1;
	for (int i = 1; i < n; i++) {
		if (arr[i] < arr[tail[0]]) {
			tail[0] = i;
		}
		else if (arr[i] > arr[tail[len-1]]) {
			prev[i] = tail[len-1];
			tail[len++] = i;
		}
		else {
			int pos = bsearch(arr, tail, -1, len-1, arr[i]);
			prev[i] = tail[pos-1];
			tail[pos] = i;
		}
	}

	cout << "NRP u obrnutom poretku" << endl;
	for (int i = tail[len-1]; i >= 0; i = prev[i])
		cout << arr[i] << " ";
	cout << endl;

	return len;
}