# PROBLEM LINK:

* Author:* Himanshu

# DIFFICULTY:

EASY

# PREREQUISITES:

# PROBLEM:

Given a value of n and a permutation which consist all the distinct values such that (1 <= ai <= n). Find out the maximum element wise remainder sum by choosing a permutation of your own following the condition that the permutation should have distinct values and (1 <= ai <= n).

# QUICK EXPLANATION:

Key to AC: n * (n - 1) / 2

# EXPLANATION:

The remainder of A divided by B is expressed as A mod B. If we express it as -

(1 mod 2) + (2 mod 3) +… + ((N1) mod N) + (N mod 1) = 1 + 2 + … + N1 =N * (N - 1) / 2

It is best to choose a permutation. This is explained below.

The selected permutation 1, 2, …, N just each 1 appeared one by times.

Suppose appears at the *x _{i}*

^{th}position of the permutation . Then the objective function (the one we want to maximize ) is

_{1}mod 1) + (x

_{2}mod 2) + ... + ( x

_{N}mod N)

When attention is paid to the sections at most each term is 0 *,* 1 *,* 2 *, …, N -* 1.

*If x _{i}* =

*i −*1 and the remaining

*N*is

*x*

_{1}=

*N*, then

### COMPLEXITY:

O(N)