Problem Statement

You are given n software modules. The difficulty of the i -th module is difficulty[i] . All of the modules have to be distributed among three deployment servers, numbered 1, 2 and 3, under these rules: Every server must receive at least one module. Every module must be given to exactly one server. After the distribution is fixed, exactly one module is selected from each server. If d1 , d2 and d3 are the difficulties of the modules selected from server 1, server 2 and server 3 respectively, the deployment difficulty of that selection is |d1 - d2| + |d2 - d3| Note that the three servers are not interchangeable in this formula — server 2 sits in the middle of both absolute differences. For a fixed distribution the deployment team always picks the selection that minimises the deployment difficulty; call that minimum the cost of the distribution. Your task: over all valid distributions of the modules among the three servers, report the maximum possible cost. Input format The first lin