#include<stdio.h>

#define MAX 100000
 
void swap( int *pa, int *pb )
{
	int t;
	
	t=*pa;
	*pa=*pb;
	*pb=t;
	
	return;
}

int partition( int A[], int p, int r )
{
	int x;
	int i,j;
	
	x=A[r];
	i=p-1;
	for( j=p; j<r; j++ ) {
		if( A[j] <= x ) {
			i++;
			swap( &A[i], &A[j] );
		}
	}
	swap( &A[i+1], &A[r] );
	
	return i+1;
}