Description

CYD’s heart can be seen as an annulus. On both the outer and inner circle, there are $N$ points placed evenly in the clockwise direction, and the points are paired one-to-one by their angles. When he sees the $i$-th hole, he recalls the $A_i$-th memory, which leaves a scar between the $i$-th point on the outer circle and the $A_i$-th point on the inner circle. The scar is drawn clockwise if $i < A_i$, counterclockwise if $i > A_i$, and straight through (radially aligned) if $i = A_i$.

CYD believes his heart can no longer be broken, so he asks you to write a program to determine a permutation $A$ of $\{1, 2, \dots, N\}$ that maximizes the number of pieces his heart shatters into.

Input Format

The first line contains a positive integer $N$.

Output Format

Output a single positive integer — the maximum number of pieces CYD’s heart can be shattered into.

2

3

3

5

4

9

Hint

Constraints:

• For 50% of the testdata, $N \le 50$.
• For 70% of the testdata, $N \le 233$.
• For 100% of the testdata, $N \le 2333$.

/* P.S. Sample explanations */

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 are concurrent.

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

Translated by ChatGPT 5