Malvika의 고양이들도 지루해하다
시간 제한1초메모리 제한1024 MB
막대 길이가 순서대로 주어질 때, 고른 막대와 역전쌍을 이루는 막대를 함께 먹는 방식으로 모든 막대를 먹는 최소 선택 횟수를 구합니다.
문제
Malvika의 고양이 Chingam과 Jimma도 문제 푸는 일에 질려 있다. 다행히 Chingam이 폭은 모두 같고 길이만 다른 다크 초콜릿 막대 개를 찾았다. 어떤 두 막대의 길이도 같지 않다. 막대들은 한 줄로 놓여 있으며, 왼쪽에서 오른쪽으로 길이가 이다. 즉 번째 막대의 길이는 이다.
Chingam은 Jimma와 간단한 게임을 하기로 했다. 한 단계마다 Jimma는 아직 먹히지 않은 막대 하나를 고른다. Chingam은 역전 쌍을 싫어하므로, 고른 막대를 즉시 먹고 그 막대와 역전 쌍을 이루는 다른 막대도 모두 먹는다. 막대 와 는 왼쪽 막대가 오른쪽 막대보다 길 때 역전 쌍을 이룬다.
즉 Jimma가 막대 를 고르면, Chingam은 막대 와 함께 이고 인 모든 막대 , 이고 인 모든 막대 를 먹는다. 이 단계가 끝나면 다음 단계에서 Jimma가 다른 막대를 고르고, 같은 과정이 반복된다. 모든 막대가 먹히면 게임이 끝난다.
Jimma는 초콜릿을 하나도 받지 못하기 때문에 이 게임이 마음에 들지 않는다. 그래서 가능한 한 빨리 게임을 끝내고 다시 자러 가고 싶어 한다. 게임이 끝날 때까지 필요한 단계 수의 최솟값을 구하라.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 첫 줄에는 정수 이 하나 주어진다.
둘째 줄에는 을 나타내는 공백으로 구분된 정수 개가 주어진다.
출력
각 테스트 케이스마다 게임이 끝날 때까지 필요한 단계 수의 최솟값을 한 줄에 하나의 정수로 출력한다.
제한
힌트
첫 단계에서 Jimma는 길이가 2인 4번 막대를 고를 수 있다. 3번 막대와 1번 막대가 4번 막대와 역전 쌍을 이루므로, Chingam은 이 막대 세 개를 모두 먹는다. 두 번째 단계에서 Jimma가 2번 막대를 고르면 게임이 끝난다. 네 막대를 한 단계에 모두 없앨 수는 없다는 것도 확인할 수 있다.