Given a sorted array of positive integers, rearrange the array alternately i.e first element should be the maximum value, second minimum value, third-second max, fourth-second min and so on.

Examples:

Input : arr[] = {1, 2, 3, 4, 5, 6, 7} Output : arr[] = {7, 1, 6, 2, 5, 3, 4}

Input : arr[] = {1, 2, 3, 4, 5, 6} Output : arr[] = {6, 1, 5, 2, 4, 3}

I am unable to solve the problem linear time.Please help me.