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 IS(int *A, int N, int key) {
    int m, l = 0, r = N - 1;
    while (A[l] <= key && A[r] >= key) {
        m = l + ((key - A[l])*(r - l)) / (A[r] - A[l]);
        if (A[m] < key) l = m + 1;
        else if (A[m] > key) r = m - 1;
        else {
            l = m;
            break;
        }
    }
    if (A[l] == key) return l; else return -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 << IS(arr, n, a) << endl << endl;
    free(arr);
    return 0;
}