# ZeroJudge - e001: 9608 連的士兵
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=e001
###### tags: `ZeroJudge` `模擬`

#include <iostream>
#include <algorithm>
using namespace std;

struct soldier {
	int height, number;
	soldier *left, *right;

	bool operator<(const soldier &other) const {
		return this->height < other.height;
	}
} soldiers[300005];

int mapped[300005];

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int amount, queries, callout;
	cin >> amount >> queries;
	for (int i = 1; i <= amount; ++i) {
		cin >> soldiers[i].height;
		soldiers[i].number = i;
	}
	sort(soldiers + 1, soldiers + amount + 1);
	for (int i = 1; i <= amount; ++i) {
		soldiers[i].left = &soldiers[i - 1];
		soldiers[i].right = &soldiers[i + 1];
		mapped[soldiers[i].number] = i;
	}
	while (queries--) {
		cin >> callout;
		callout = mapped[callout];
		cout << soldiers[callout].left->number << ' ' << soldiers[callout].right->number << '\n';
		soldiers[callout].left->right = soldiers[callout].right;
		soldiers[callout].right->left = soldiers[callout].left;
	}
}