시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB62233.333%

문제

Fredrik har just ställt ut nya blommor på sin fönsterbräda. Men någonting känns lite fel. Det är inte riktigt så symmetriskt som han skulle vilja ha det.

Det finns $K$ olika blomsorter och varje sort beskrivs av ett av heltalen $1,2,...,K$. Fönsterbrädan har $N$ blommor utställda på rad från vänster till höger. Den $i$:te blomman från vänster är av sort $a_i$. Fredrik vill att blommorna ska vara symmetriska, d.v.s att $a_i=a_{N+1-i}$ gäller för alla $i$. För att åstakomma detta tänker han göra drag som byter plats på två intilliggande blommor. Ett drag kan alltså byta plats på blomma $i$ och blomma $i+1$ för något $1\le i \le N-1$.

Vad är minsta antalet drag som krävs för att uppnå blomsymmetri?

입력

Den första raden av indata innehåller två heltal $N$ och $K$ ($1 \le N,K \le 200 000$): antalet blomor på fönsterbrädan och totala antalet sorter som finns. Därefter följer en rad med $N$ heltal $a_1,a_2,...,a_N$ ($1\le a_i \le K$): blommorna på fönsterbrädan.

Det garanteras att det finns en sekvens av drag som ordnar blommorna symmetriskt.

출력

Skriv ut ett tal: det minsta möjliga antalet drag för att uppnå blomsymmetri.

예제 입력 1

4 5
5 5 2 2

예제 출력 1

2

예제 입력 2

8 3
3 1 1 1 2 3 1 2

예제 출력 2

5

예제 입력 3

7 3
1 3 2 1 2 2 2

예제 출력 3

5

힌트

I det första exemplet kan vi börja med att byta plats på blomma 2 och 3, och sedan på blomma 1 och 2. Då kommer blommorna hamna i ordningen 1 3 3 1.

I det andra exemplet kan vi till exempel göra följande 5 byten i ordning: 4 och 5, 3 och 4, 1 och 2, 2 och 3, 7 och 8. Då kommer blommorna hamna i ordningen 1 2 3 1 1 3 2 1.

출처

Olympiad > Swedish Olympiad in Informatics > 2021 > KATT ?번

  • 문제를 만든 사람: Fredrik Ekholm