P4903 Heartbreak

NOIP 2015 preliminary round. CYD dashi (大神) failed miserably at his alma mater. On that day, he went back to visit his old classroom and found that the desk riddled with $N$ holes was still there — it was the desk he used to share with classmate XHY in middle school. At that moment, CYD’s heart shattered.

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.

The first line contains a positive integer $N$.

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

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