该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

N个数字按升序排好去参加相亲大会，其权值为1到N 。

如果N是偶数，则均分成两半

如果N是奇数，则前一半为N/2+1个数字，后一半为N/2个数字

就这样不断分下去

当某个区间有3个数字时，则前两个进行匹配，代价为其数字的乘积，第3个数字则派发好人卡，伤心的回家。 如果只有2个数字，则直接进行匹配。

问整个活动办下来，总代价是多少。

Format

Input

第一行给出数字N，N<=2200

Output

如题

Samples

11

188

Hint

对于样例

总代价为2+20+56+110=188