P10295 [CCC 2024 S1] Hat Circle

At a recent party, $N$ people are sitting around a round table, where $N$ is even. The seats are numbered $1$ to $N$ in clockwise order. Each person is wearing a hat with a number written on it. Specifically, the person in seat $i$ is wearing a hat with the number $H_i$ on it. Each person is looking at the person directly opposite them in the circle. Please find the number of people who see a hat with the same number as their own.

The first line contains a positive even integer $N$, the number of people at the party. The next $N$ lines each contain a non-negative integer $H_i$, representing the number written on the hat of person $i$.

Output one integer, the number of people who see a hat with the same number as their own.

**[Sample 1 Explanation]** The arrangement of the four seats around the table is shown in the figure below. The number inside each circle is the number on that person’s hat, and the number next to the circle is that person’s index. Note that each person sees a number equal to the number on their own hat. The people in positions $1$ and $3$ both see the number $0$, and the people in positions $2$ and $4$ both see the number $1$.  **[Sample 2 Explanation]** The arrangement of the four seats around the table is shown in the figure below. The number inside each circle is the number on that person’s hat, and the number next to the circle is that person’s index. Note that each person sees a number that is not equal to the number on their own hat. The people in positions $1$ and $4$ both see the number $0$, and the people in positions $2$ and $3$ both see the number $1$.  **[Constraints]** **This problem uses bundled testdata.** For all testdata, it is guaranteed that $1\leq N\leq 10^6$ and $0\leq H_i\leq 2\times 10^6$. The table below shows the distribution of the $15$ points: | Score | Description | Range of $N$ | Range of $H_i$ | | :-: | :- | :-: | :-: | | $2$ | Very few people; only two possible hat numbers | $N \leq 4$ | $H_i \leq 1$ | | $1$ | Only one possible hat number | $N \leq 100$ | $H_i = 1$ | | $2$ | People in odd positions have hat number $1$, and people in even positions have hat number $0$ | $N \leq 100$ | $H_i \leq 1$ | | $5$ | A medium number of people | $N \leq 2 \times 10^3$ | $H_i \leq 4 \times 10^3$ | | $5$ | Many people and many possible hat numbers | $N \leq 10^6$ | $H_i \leq 2 \times 10^6$ | Translated by ChatGPT 5