Courses

데이터 구조

데카르트 트리

Module: 데카르트 트리

Problem

3 /3

카트 분류

Problem

<사업부> <사업부> 취소 Akaki는 n개의 카드로 구성된 덱입니다. 각 카드에는 정확히 1에서 100 000까지의 정수가 쓰여 있습니다. 일부 카드에 같은 숫자가 쓰여 있을 가능성이 있습니다.

<사업부> Akaki는 덱의 모든 카드를 정렬하기로 결정했습니다. 이를 위해 그는 덱에서 맨 위 카드 한 장을 차례로 가져오고 덱의 나머지 모든 숫자 중 최소값에 적힌 숫자가 같으면 이 카드를 옆에 둡니다. 그렇지 않으면 Akaki는 이 카드를 덱 맨 아래에 놓고 덱 맨 위에서 다음 카드를 뽑습니다. 데크에 남은 카드가 없으면 프로세스가 종료됩니다. Akaki는 언제든지 덱에 남아 있는 일부 카드에 적힌 최소 수를 알고 있지만 이 카드(또는 카드들)가 덱에서 어디에 있는지는 모른다고 가정할 수 있습니다.

<사업부> 당신의 임무는 Akaki가 데크에서 맨 위 카드를 보는 총 횟수를 결정하는 것입니다.

<사업부>

<사업부> 입력

<사업부> 첫 번째 줄 다음에는 양의 정수 n (1 ≤ n ≤ 100 000) — 덱의 카드 수.

<사업부> 두 번째 줄에는 n 양의 정수 a₁, a₂, ..., a_n ( 1 ≤ a_i ≤ 100 000), 여기서 a_i는 i번째 상단 카드에 적힌 숫자와 같습니다. 데크.< /div> <사업부>

<사업부> 출력

<사업부>

<사업부> Akaki가 덱의 맨 위 카드를 본 총 횟수를 인쇄합니다.

<몸>

<사업부> 참고 <사업부> 첫 번째 예에서 Akaki는 먼저 6번 카드를 보고 덱 맨 아래에 놓은 다음 3번 카드도 덱 맨 아래에 놓은 다음 숫자 1. 데크에 남아 있는 최소 숫자가 포함되어 있으므로 숫자 1이 있는 카드를 따로 둡니다. 그런 다음 덱의 카드는 위에서 아래로 [2, 6, 3] 순서로 놓입니다. 그 후 Akaki는 숫자 2가 있는 맨 위 카드를 보고 옆에 둡니다. 그런 다음 덱의 카드는 위에서 아래로 [6, 3] 순서로 놓입니다. 그런 다음 Akaki는 6 번 카드를보고 데크 맨 아래에 놓은 다음 3 번 카드를 따로 보관합니다. 그 후 숫자 6의 카드 한 장이 데크에 남아 아카키가보고 따로 보관합니다. 따라서 Akaki는 7장의 카드를 볼 것입니다. <사업부> <사업부> (c) 쿠르바토프 E., 2018

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking