View Code of Problem 134

#include <stdio.h>
 
struct num{
	int data;
	int pos;
};
 
struct num arr[100001];
 
int Partition(struct num arr[], int low, int high){
	int p1 = arr[low].data;
	int p2 = arr[low].pos;
	while(low<high){
		while(low<high && arr[high].data>=p1) --high;
		arr[low].data = arr[high].data;
		arr[low].pos = arr[high].pos;
		while(low<high && arr[low].data<=p1) ++low;
		arr[high].data = arr[low].data;
		arr[high].pos = arr[low].pos;
	}
	arr[low].data = p1;
	arr[low].pos = p2;
	return low;
}
 
void QuickSort(struct num arr[], int low, int high){
	if(low<high){
		int pivot = Partition(arr, low, high);
		QuickSort(arr, low, pivot-1);
		QuickSort(arr, pivot+1, high);
	}
}
 
 
 
int main(){
	int n,q,l,r,min;
	//输入1：1个整数n，n个整数，1<=n<=100000 
	while(scanf("%d", &n)!=EOF){
		for(int i=1; i<=n; i++){
			scanf("%d", &arr[i].data);
			arr[i].pos = i;
		}
		QuickSort(arr, 1, n);
		//输出2：1个整数q，q组整数 
		scanf("%d", &q);
		for(int i=0; i<q; i++){
			scanf("%d %d", &l, &r);
			//处理：遍历数组，输出l~r区间的第一个数 
			for(int j=1; j<=n; j++){
				if(l<=arr[j].pos && arr[j].pos<=r){
					//输出：q个整数
					printf("%d\n", arr[j].data);
					break;
				}
			}
		}
	}
	return 0; 
}