한 줄로 나열된 \(N(1\le N\le 200\;000)\)개의 전구가 있다. 모든 전구에는 양의 정수가 주어져 있으며, 맨 왼쪽 전구가 \(1\)번 전구이고, 맨 오른쪽 전구가 \(N\)번 전구이다. 전구의 상태는 2가지이며, 켜져 있거나 꺼져 있거나 둘 중 하나이다.
당신은 다음 두 가지 시행을 원하는 순서로 여러 번 시행하여 '예쁜 모양'을 만들려고 한다.
* \(N\) 이하의 양의 정수 \(i\)를 골라, \(1\)번부터 \(i\)번까지의 전구를 켠다. 이 시행에는 시간이 0분 걸린다.
* \(N\) 이하의 양의 정수 \(i\)를 골라, \(i\)번 전구의 상태를 반전시킨다 (켜져있으면 끄고, 꺼져있으면 켠다). 이 시행에는 시간이 1분 걸린다.
처음에 모든 전구는 꺼진 상태이다. '예쁜 모양'을 만드는데 걸리는 최소 시간을 출력하라.
<입력>
첫 줄에 문제에 언급된 정수 \(N\)이 주어진다.
두번째 줄에 '예쁜 모양'을 나타내는 정수 \(N\)개가 공백으로 구분되어 주어진다. \(i\)번째 정수 \(A_i\)는 \(i\)번 전구가 켜져 있어야 하면 \(1\)이고, 꺼져 있어야 하면 \(0\)이다.
iktk 2년 전 2
<문제>
한 줄로 나열된 \(N(1\le N\le 200\;000)\)개의 전구가 있다. 모든 전구에는 양의 정수가 주어져 있으며, 맨 왼쪽 전구가 \(1\)번 전구이고, 맨 오른쪽 전구가 \(N\)번 전구이다. 전구의 상태는 2가지이며, 켜져 있거나 꺼져 있거나 둘 중 하나이다.
당신은 다음 두 가지 시행을 원하는 순서로 여러 번 시행하여 '예쁜 모양'을 만들려고 한다.
* \(N\) 이하의 양의 정수 \(i\)를 골라, \(1\)번부터 \(i\)번까지의 전구를 켠다. 이 시행에는 시간이 0분 걸린다.
* \(N\) 이하의 양의 정수 \(i\)를 골라, \(i\)번 전구의 상태를 반전시킨다 (켜져있으면 끄고, 꺼져있으면 켠다). 이 시행에는 시간이 1분 걸린다.
처음에 모든 전구는 꺼진 상태이다. '예쁜 모양'을 만드는데 걸리는 최소 시간을 출력하라.
<입력>
첫 줄에 문제에 언급된 정수 \(N\)이 주어진다.
두번째 줄에 '예쁜 모양'을 나타내는 정수 \(N\)개가 공백으로 구분되어 주어진다. \(i\)번째 정수 \(A_i\)는 \(i\)번 전구가 켜져 있어야 하면 \(1\)이고, 꺼져 있어야 하면 \(0\)이다.
<출력>
'예쁜 모양'을 만드는데 걸리는 최소 시간을 분단위 정수로 출력한다.