View Code of Problem 134

#include <stdio.h>
#include <stdlib.h>

struct num{
	int data;
	int pos;
};

struct num arr[100005];

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 p = Partition(arr, low, high);
		QuickSort(arr, low, p-1);
		QuickSort(arr, p+1, high);
	}
}

int main(){
	int n,q,l,r;
	//输入：1个整数n，n个整数，1<=n<=100000 
	while(scanf("%d", &n)!=EOF){
		for(int i=0; i<n; i++){
			scanf("%d", &arr[i].data);
			arr[i].pos = i+1;
		}
		//处理1：对数组快排
		QuickSort(arr, 0, n-1);
		//输入：1个整数q，q对整数，1<=q<=100000
		scanf("%d", &q);
		while(q--){
			scanf("%d %d", &l, &r);
			//处理2：遍历数组，输出第一个满足条件的数值 
			for(int i=0; i<n; i++){
				if(l<=arr[i].pos && arr[i].pos<=r){
					//输出：1个整数 
					printf("%d\n", arr[i].data);
					break;
				}
			}
		}
		
		
	}
	
	
}