### PROBLEM LINK:

* Author:* Shashwat Chandra

*Bharat Goyal, Shashwat Chandra, Taranpreet Singh*

**Tester:***Bharat Goyal*

**Editorialist:**### DIFFICULTY

Cakewalk

### PREREQUISITES

Observations

### PROBLEM

Given an array A of distinct numbers, find the maximum value of (((A_1 \bmod A_2) \bmod A_3)......) \bmod A_N over all possible orderings of (A_1, A_2, \ldots, A_N)

### QUICK EXPLANATION

If the minimum element, say X, isn’t the first element of the sequence, then the value is guaranteed to be less than X. However, if we set X as the first element and calculate the expression, it always come out to be X.

### EXPLANATION

Observe that for any given order A_1...A_n, the value of the expressions is bounded by min(A_2 \ldots A_n) - 1. Consider the smallest element of the sequence, X. If it is anywhere in the 2 to n range, then the expression is guaranteed to be smaller than X. Let us place X at the first position. It can be observed that X \bmod A_i for all valid i is guaranteed to be X (it’s the smallest value). Therefore, placing X at the first position is guaranteed to give us the right answer. The order of the remaining elements is irrelevant as X stays the same under the modulo condition.

### Complexity

O(N)