35510번 - Good Bye, Scenery!

https://www.acmicpc.net/problem/14640

Images by John Fowler, Carol Highsmith, and Richard Woodland

당신은 $N$명의 사진가와 함께 Rapid City로 떠난 여행의 하루를 South Dakota Badlands의 사진을 찍는 데 보내기로 했다. 배드랜즈는 장엄하고 독특한 지형으로 유명한 곳이다. 사진가들은 아마추어 사진가이지만, 촬영 조건에 대해서는 누구보다 까다롭다.

세심하게 조사한 끝에, 당신은 배드랜즈에서 그림 같은 풍경으로 둘러싸인 아름다운 지역을 발견했다. 이 지역에는 사진을 찍을 수 있는 명당이 앞에서부터 차례로 한 줄로 $N$개 놓여 있으며, 각 명당에서는 한 명의 사진가만이 사진을 찍을 수 있다.

현재 이 지역에는 $N$명의 사진가가 한 줄로 서 있다. 앞에서부터 $i$번째에 서 있는 사진가는 앞에서부터 $1$번째 명당부터 $A_i$번째 명당 중 어느 한 곳에서 사진을 찍고 싶어 한다. 그보다 뒤쪽의 명당은 햇빛의 방향이 맞지 않아 원하는 사진을 얻을 수 없기 때문이다.

$N$명의 사진가 모두가 자신이 원하는 범위 안의 명당에서 사진을 찍을 수 있도록, 당신은 줄에서 인접한 두 사진가의 자리를 바꿀 수 있다. 자리를 바꾼 뒤에는 앞에서부터 $i$번째에 서 있는 사진가가 앞에서부터 $i$번째 명당을 사용하게 된다. 모든 사진가가 자신이 원하는 조건을 만족하도록 하기 위해 필요한 최소 교환 횟수를 구하여라.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

첫째 줄에 사진가의 수를 나타내는 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. $A_i$는 현재 앞에서부터 $i$번째에 서 있는 사진가가 앞에서부터 $1$번째 명당부터 $A_i$번째 명당 중 한 곳에서 사진을 찍고 싶어 함을 의미한다.

각 테스트 케이스마다 한 줄씩, 모든 사진가가 자신의 조건을 만족하도록 만들기 위해 필요한 최소 교환 횟수를 출력한다. 불가능한 경우에는 $-1$을 출력한다.

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