View Code of Problem 134

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

struct num{
	int value;
	int xh;
};
struct num nums[100005];

int partition(struct num nums[],int low,int high){
	int p1,p2;
	p1 = nums[low].value;
	p2 = nums[low].xh;
	while(low<high){
		while(low<high && nums[high].value >= p1)
			high--;
		nums[low].value = nums[high].value;
		nums[low].xh = nums[high].xh;

		while(low<high && nums[low].value <= p1)
			low++;
		nums[high].value = nums[low].value;
		nums[high].xh = nums[low].xh;
	}

	nums[low].value = p1;
	nums[low].xh = p2;
	return low;
}

void quicksort(struct num nums[],int low,int high){ 
	if(low<high){
		int k = partition(nums,low,high);
		quicksort(nums,low,k-1);
		quicksort(nums,k+1,high);
	}


}


int main(){
	int n;
	while((scanf("%d",&n)!=EOF)){
		for(int i=0; i<n; i++){
			scanf("%d",&nums[i].value);
			nums[i].xh = i+1;
		}

		quicksort(nums,0,n-1);
		int order;
		scanf("%d",&order);
		while(order--){
			int l,r;
			scanf("%d %d",&l,&r);
			for(int i=0;i<n;i++){
				if(nums[i].xh>=l && nums[i].xh<=r){
					printf("%d\n",nums[i].value);
					break;
				}
			}
		
		}

	
	
	}

	return 0;
}