Optimal Item Distribution Game

Problem Statement

Optimal Item Distribution Game Problem Description Player A owns n items. Item i has a positive weight arr[i] , where i runs from 1 to n. Player A also has three distinct containers, labelled 1, 2 and 3, all initially empty. Player A must place every item into exactly one container, and every container must end up holding at least one item. Player B is then shown the finished distribution and takes exactly one item out of each container. Let w1 , w2 and w3 be the weights of the items Player B takes from containers 1, 2 and 3 respectively. The score of the game is |w1 - w2| + |w2 - w3| , where |x| is the absolute value of x . Player B always picks the three items so that the score is as small as possible. Player A distributes the items so that the score Player B is forced to leave behind is as large as possible. Report that score. Input Format The input consists of two lines. The first line contains a single integer n , the number of items. The second line contains n space-separated int