Problem Background

NOIP2015 Preliminary Round. CYD the Great fell at his alma mater. On the day of the preliminary round, he visited his old classroom and found that the desk with N holes was still there—the desk he used to sit at with classmate XHY during junior high. At this sight, CYD's heart shattered.

Problem Description

CYD's heart can be visualized as a ring with N points evenly distributed both on the inner and outer sides, corresponding to each other. When he sees the i-th hole, he recalls the i-th memory, which leaves a scar between the i-th point on the outer side and the A_i-th point on the inner side of his heart (clockwise when i < A_i, counterclockwise when i > A_i, and directly corresponding when i = A_i).

CYD believes his heart will not break again, so he wants you to write a program to determine a permutation of A_i that maximizes the number of pieces his heart shatters into.

Input Format

The first line contains a single positive integer N.

Output Format

Output a single line containing a positive integer representing the maximum number of pieces CYD's heart can shatter into.

Sample Input and Output

Sample Input #1

2

Sample Output #1

3

Sample Input #2

3

Sample Output #2

5

Sample Input #3

4

Sample Output #3

9

Notes

For 40% of the data, for the first i10%, N <= i5.

For 50% of the data, N <= 50.

For 70% of the data, N <= 233.

For 100% of the data, N <= 2333.

/ P.S. Sample Explanation /

Sample 1: 1->2, 2->1

Sample 2: 1->2, 2->3, 3->1. Note: If 1->3, 2->2, 3->1, then the three lines intersect at a single point.

Sample 3: 1->3, 2->4, 3->2, 4->1

见题面 Input 部分

见题面 Output 部分