2

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

using namespace std;

void print(int *arr, int n) {
	for (int i = 0; i < n; ++ i)
		cout << arr[i] << " ";
	cout << endl;
}

int LS(int *arr, int n, int e) {
	int res = -1;
	for (int i = 0; i < n; ++ i) {
		if (arr[i] == e) res = i;
	}
	return res;
}

void QSort(int *arr, int n) {
	if (n == 1) return;
	int l = 0;
	int r = n - 1;
	int pivot = (l + r + 1) / 2;
	while (l < r) {
		while (l < pivot && arr[l] <= arr[pivot]) ++ l;
		while (r > pivot && arr[r] >= arr[pivot]) -- r;
		if (l >= r) continue;
		swap(arr[l], arr[r]);
		if (l == pivot) pivot = r;
		else if (r == pivot) pivot = l;
	}
	QSort(arr, pivot);
	QSort(arr + pivot, n - pivot);
}

int BS(int *arr, int n, int e) {
	int l = 0;
	int r = n;
	while (r - l > 1) {
		int m = (r + l) / 2;
		if (e < arr[m])
			r = m;
		else
			l = m;
	}
	return ((e == arr[l]) ? l : -1);
}

int main(void) {
	srand(time(NULL));
	int n;
	cin >> n;
	int *arr = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; ++ i) {
		arr[i] = rand() % 100;
	}
	print(arr, n);
	cout << "> ";
	int a;
	cin >> a;
	cout << LS(arr, n, a) << endl << endl;
	QSort(arr, n);
	print(arr, n);
	cout << "> ";
	cin >> a;
	cout << BS(arr, n, a) << endl << endl;
	free(arr);
	return 0;
}