P8641 [Lanqiao Cup 2016 National C] Winning Tickets.

An organization is holding a ticket grand prize game. Winning contestants have a chance to win several tickets. The host takes out $N$ cards (labeled with the numbers $1 \sim N$), shuffles them, and arranges them in a circle. You may start from any card and count clockwise: $1,2,3 \cdots$. If the number you count is exactly the same as the number on the current card, you take that card. Then restart counting from the next card. The game ends when you can no longer take any card. The sum of the numbers on the cards you have taken is the number of tickets you win. For example: The card order is: $1,2,3$. If we start counting from card $1$, we take card $1$. Then we start from card $2$, but the counted numbers can no longer match the card numbers. Soon the counted numbers become larger and larger, and it is impossible to take any more cards. So this time we win only $1$ ticket. That is not too bad. If we foolishly start counting from card $2$ or $3$, we cannot get any card at all. If we are lucky and the card order is $2,1,3$. Then we can successfully take all the cards. The goal of this problem is: given the clockwise card sequence, you may start counting from anywhere. Find the maximum number of tickets you can win (i.e., the sum of the numbers on the cards you take).

The first line contains an integer $N(N

One line with one integer, the maximum number of tickets you can win in the best case.

Time limit: 1 s, 256 MB. Lanqiao Cup 2016, the 7th National Final. Translated by ChatGPT 5