35513번 - Good Bye, 요세푸스 문제!

https://www.acmicpc.net/workbook/view/6520

마지막 요세푸스 문제는 다음과 같다.

$1$번부터 $N$번까지의 번호가 매겨진 $N$명의 사람들이 긴 탁자에 일렬로 앉아 있다. 처음에 $i$번째 자리에는 $A_i$번 사람이 앉아 있다.

현재 탁자에 앉아 있는 사람 중 양 끝에 앉아 있지 않은 사람을 한 명 고른다. 고른 사람의 번호를 $k$, 그 사람의 왼쪽과 오른쪽에 가장 가까이 앉아 있는 사람의 번호를 각각 $l,r$이라고 하자. $l>k<r$ 또는 $l<k>r$을 만족한다면, $k$번 사람을 탁자에서 제거할 수 있다.

사람이 제거된 뒤에는 남은 사람들이 기존의 상대적인 순서를 유지한 채 다시 일렬로 앉아 있는 것으로 본다.

위 연산을 원하는 만큼 수행할 때, 마지막까지 탁자에 앉아 있는 사람 수의 최솟값을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어지고, 다음 줄부터 각 테스트 케이스의 입력이 차례대로 주어진다.

각 테스트 케이스의 첫째 줄에 정수 $N$이 주어진다.

각 테스트 케이스의 둘째 줄에 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다.

$T$개의 줄에 각 테스트 케이스에 대한 정답을 차례대로 출력한다.

• $1\leq T\leq 300\,000$
• $2\leq N\leq 300\,000$
• 모든 테스트 케이스에서 $N$의 합은 $300\, 000$ 이하이다.
• $1\leq A_i\leq N$ ($1\leq i\leq N$)
• $A_i\neq A_j$ ($1\leq i<j\leq N$)