#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000010];  // 全局数组，用于存储要查找的升序序列（数组下标从1开始）

/**
 * 功能简介：检查数字x是否在数组中出现过（只判断是否存在，不关心位置）
 * 参数：x 是要查找的目标数字
 * 返回值：如果找到x，返回1（表示存在）；如果没找到，返回-1（表示不存在）
 * 注意事项：
 *   1. 从数组中间位置开始比较，一旦找到x就立刻确认存在并结束查找
 *   2. 如果中间元素比x大，说明x只能在左半部分，缩小右边界
 *   3. 如果中间元素比x小，说明x只能在右半部分，扩大左边界
 *   4. 要是把整个数组都找完了还没见到x，就返回-1
 */
int bs1(int x) {
	int l = 1, r = n;  // 左边界初始化为1，右边界初始化为数组长度n
	int ans = -1;      // 结果初始化为-1（默认不存在）
	while (l <= r) {   // 只要左边界没超过右边界，就继续查找
		int m = (l + r) / 2;  // 计算中间位置（整数除法）
		if (a[m] == x) {      // 中间元素正好是要找的x
			ans = 1;          // 标记为存在
			break;            // 找到就直接退出循环，不用再找了
		} else if (a[m] > x) { // 中间元素比x大
			r = m - 1;        // 缩小右边界，去左半部分找
		} else {              // 中间元素比x小
			l = m + 1;        // 扩大左边界，去右半部分找
		}
	}
	return ans;  // 返回查找结果
}

/**
 * 功能简介：查找x在数组中第一次出现的位置（最左边的位置）
 * 参数：x 是要查找的目标数字
 * 返回值：找到的话返回第一次出现的下标（下标从1开始）；没找到返回-1
 * 注意事项：
 *   1. 找到x时不马上结束，而是继续往左边找（缩小右边界），确保找到最左边的x
 *   2. 其他情况和基础二分查找一样：中间元素比x大就往左找，比x小就往右找
 */
int bs2(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] == x) {      // 找到x了
			ans = m;          // 先记录当前位置
			r = m - 1;        // 继续往左找，看看有没有更左边的x
		} else if (a[m] > x) {
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	return ans;  // 最终结果是最左边x的位置（没找到就是-1）
}

/**
 * 功能简介：查找x在数组中最后一次出现的位置（最右边的位置）
 * 参数：x 是要查找的目标数字
 * 返回值：找到的话返回最后一次出现的下标（下标从1开始）；没找到返回-1
 * 注意事项：
 *   1. 找到x时不马上结束，而是继续往右边找（扩大左边界），确保找到最右边的x
 *   2. 其他情况和基础二分查找一样：中间元素比x大就往左找，比x小就往右找
 */
int bs3(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] == x) {      // 找到x了
			ans = m;          // 先记录当前位置
			l = m + 1;        // 继续往右找，看看有没有更右边的x
		} else if (a[m] > x) {
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	return ans;  // 最终结果是最右边x的位置（没找到就是-1）
}

/**
 * 功能简介：查找大于x的元素中，第一次出现的位置（第一个比x大的元素在哪里）
 * 参数：x 是作为参考的目标数字
 * 返回值：找到的话返回对应下标（下标从1开始）；如果所有元素都小于等于x，返回-1
 * 注意事项：
 *   1. 只有中间元素比x大时，才记录位置，并且尝试往左找（可能有更左边的符合条件的元素）
 *   2. 如果中间元素等于或小于x，说明目标在右边，就扩大左边界
 *   3. 最终结果是第一个比x大的元素位置
 */
int bs4(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] > x) {       // 中间元素比x大（符合条件）
			ans = m;          // 记录当前位置
			r = m - 1;        // 往左找，看看有没有更左边的符合条件的元素
		} else {              // 中间元素等于或小于x（不符合条件）
			l = m + 1;        // 往右找
		}
	}
	return ans;
}

/**
 * 功能简介：查找大于等于x的元素中，第一次出现的位置（第一个不小于x的元素在哪里）
 * 参数：x 是作为参考的目标数字
 * 返回值：找到的话返回对应下标（下标从1开始）；如果所有元素都小于x，返回-1
 * 注意事项：
 *   1. 当中间元素大于等于x时，记录位置，并且尝试往左找（可能有更左边的符合条件的元素）
 *   2. 如果中间元素小于x，说明目标在右边，就扩大左边界
 *   3. 最终结果是第一个不小于x的元素位置
 */
int bs5(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] >= x) {      // 中间元素大于等于x（符合条件）
			ans = m;          // 记录当前位置
			r = m - 1;        // 往左找，看看有没有更左边的符合条件的元素
		} else {              // 中间元素小于x（不符合条件）
			l = m + 1;        // 往右找
		}
	}
	return ans;
}

/**
 * 功能简介：查找小于x的元素中，最后一次出现的位置（最后一个比x小的元素在哪里）
 * 参数：x 是作为参考的目标数字
 * 返回值：找到的话返回对应下标（下标从1开始）；如果所有元素都大于等于x，返回-1
 * 注意事项：
 *   1. 当中间元素小于x时，记录位置，并且尝试往右找（可能有更右边的符合条件的元素）
 *   2. 如果中间元素等于或大于x，说明目标在左边，就缩小右边界
 *   3. 最终结果是最后一个比x小的元素位置
 */
int bs6(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] < x) {       // 中间元素小于x（符合条件）
			ans = m;          // 记录当前位置
			l = m + 1;        // 往右找，看看有没有更右边的符合条件的元素
		} else {              // 中间元素等于或大于x（不符合条件）
			r = m - 1;        // 往左找
		}
	}
	return ans;
}

/**
 * 功能简介：查找小于等于x的元素中，最后一次出现的位置（最后一个不大于x的元素在哪里）
 * 参数：x 是作为参考的目标数字
 * 返回值：找到的话返回对应下标（下标从1开始）；如果所有元素都大于x，返回-1
 * 注意事项：
 *   1. 当中间元素小于等于x时，记录位置，并且尝试往右找（可能有更右边的符合条件的元素）
 *   2. 如果中间元素大于x，说明目标在左边，就缩小右边界
 *   3. 最终结果是最后一个不大于x的元素位置
 */
int bs7(int x) {
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (a[m] <= x) {      // 中间元素小于等于x（符合条件）
			ans = m;          // 记录当前位置
			l = m + 1;        // 往右找，看看有没有更右边的符合条件的元素
		} else {              // 中间元素大于x（不符合条件）
			r = m - 1;        // 往左找
		}
	}
	return ans;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];  // 输入数组（注意：数组下标从1开始）
	// 重要提醒：使用这些查找函数前，必须保证数组a是升序排列的！
	// 如果输入的数组无序，需要先排序，比如加上：sort(a + 1, a + n + 1);
	return 0;
}