https://codeforces.com/contest/1610/submission/136675430 이 문제를 혼자 어렵게 풀어서 (팰린드롬=배열과 뒤집은배열을 문자별로 인덱스매칭한 배열의 인버전 관리) 생각난 문제다. inversion 구한거 되돌리는 방법이 좀 까다로운거같다. 이 문제의 경우 한 문자만 전부 제거해보면 되는데, 같은 문자 내에는 inversion겹치는게 없기 때문에 지우는게 가능하다. 겹치는게 있는 경우 막 빼면 전부 다 뺐을때 음수될거다. 세그레이지같은거로 잘 관리해줘야 인버젼배열값 일관성이 유지되는듯. 위 문제는 문자를 빼는건데, 일단 인버젼문제로 치환하고 원소 하나씩 제거하는거를 풀 수 있으면 된다. dynamic inversion counting 라고 부를 수 있으려나?

NOTE: 매칭시 교차개수 = inversion count, 교차하지않는(invcnt가 0인) 최대부분집합?매칭? = LIS, 근데 위 코포문제는 LIS로 할수 없는게, a...abc인 경우 a...a에서 LIS만들고 bc가 남는거라 한번에 제거 불가능하다고 나옴. 그래서 더 힘들었고 그래서 inversion 동적관리(한번빼는거라 동적은 아니었지만)까지 도달했다.

동적 인버전 관리(뇌피셜): 원소 하나 뺄때 inv-=값 하고, 그 인버전배열에서 값은 남겨둔다. 그리고 그게 기여한 값들의 배열값에서 -1해줘야함. 모든값 distinct하면 세그레이지로 잘 관리해줄 수 있을듯.

문제: 정수배열이 주어진다. 숫자 하나 정해서 배열에서 그 값을 갖는 원소들을 전부 제거(제거 후의 빈공간은 이어붙인다)하는 연산이 가능하다. 배열을 팰린드롬으로 만들기 위한 최소 연산횟수는?
뇌피셜 풀이: 인버전개수가 제일 많은원소부터 그리디하게 제거? 같은값 있으면 아무거나? 인버전 동적관리 가능하다고 해도 이 풀이의 정당성은 전혀 다른 문제임으로 증명과 스트레스테스트까지 해보자.
뇌피셜 풀이 증명시도: exchange argument가 좋아보인다. 제일 인버전큰값 선택안한다고 해보자. 그거와 인버전을 만드는 다른 값들이 있을텐데, 그 값들은 전부 선택되어야 인버전이 0이 될 수 있다. 흠... 그래프 간선 나이브하게 다 만들면 N^2이긴 한데, 그 그래프의 최소 정점덮개문제가 되는듯. 간선하나가 인버전 하나를 나타내고, 연산선택값 하나가 정점 하나를 나타내니까. 망했네? 이분그래프에서는 풀 수 있으니까 이분그래프적인 특징 어떻게 추가 못하나...

답이없다. 문자x정해서 a와 b에서 하나씩 제거하는 연산만 가능할때 최소 횟수 묻는것도 두 제거 상대위치가 같으면 LIS가 되는데 아닌 경우가 최적일 경우가 있을듯함.