306078: CF1143A. The Doors

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

The Doors

题意翻译

## 题目描述 三年过去了,伦敦仍在下雨,布莱克先生不得不关上家里的所有门,以免被水淹没。然而,有一次天晴了,布莱克先生打开了一扇又一扇的门,直到他打开了家里所有的门。 布莱克先生家里正好有两个出口,我们把它们分别命名为左出口和右出口。每个出口都有几个门,所以布莱克先生家里的每个门要么位于左边,要么位于右边。你知道每个门的位置。最初所有的门都是关闭的。布莱克先生只有在至少一个出口的所有门都打开的情况下才能离开房子。请按照布莱克先生开门的顺序,找出最小的索引k,以便布莱克先生能在打开第一个k门后离开房子。 注意到布莱克先生最多每扇门开一次,最后所有的门都开了。 ## 输入: 第一行包含整数n(2≤n≤200000)门的数量。 下一行包含n个整数:布莱克先生开门的顺序。如果第i个打开的门位于左出口,则这些整数的第i个等于0;如果它位于右出口,则等于1。 保证左出口至少有一扇门,右出口至少有一扇门。 ## 输出: 最小的整数k,这样在布莱克先生打开第一个k门后,他就可以离开房子了。 ## 说明: ### 第一个例子: 前两个门是从左出口开的,所以当布莱克先生只打开了两个门时,左出口还有两个关闭的门,右出口有一个关闭的门。所以布莱克先生当时不能离开。 当他打开第三扇门时,右出口的所有门都打开了,所以布莱克先生可以离开房子。 ### 第二个例子: 当前两个门被打开时,每个出口都有一个打开、关闭的门。 布莱克先生开了三扇门,就可以从左边的出口出去了

题目描述

Three years have passes and nothing changed. It is still raining in London, and Mr. Black has to close all the doors in his home in order to not be flooded. Once, however, Mr. Black became so nervous that he opened one door, then another, then one more and so on until he opened all the doors in his house. There are exactly two exits from Mr. Black's house, let's name them left and right exits. There are several doors in each of the exits, so each door in Mr. Black's house is located either in the left or in the right exit. You know where each door is located. Initially all the doors are closed. Mr. Black can exit the house if and only if all doors in at least one of the exits is open. You are given a sequence in which Mr. Black opened the doors, please find the smallest index $ k $ such that Mr. Black can exit the house after opening the first $ k $ doors. We have to note that Mr. Black opened each door at most once, and in the end all doors became open.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 2 \le n \le 200\,000 $ ) — the number of doors. The next line contains $ n $ integers: the sequence in which Mr. Black opened the doors. The $ i $ -th of these integers is equal to $ 0 $ in case the $ i $ -th opened door is located in the left exit, and it is equal to $ 1 $ in case it is in the right exit. It is guaranteed that there is at least one door located in the left exit and there is at least one door located in the right exit.

输出格式


Print the smallest integer $ k $ such that after Mr. Black opened the first $ k $ doors, he was able to exit the house.

输入输出样例

输入样例 #1

5
0 0 1 0 0

输出样例 #1

3

输入样例 #2

4
1 0 0 1

输出样例 #2

3

说明

In the first example the first two doors are from the left exit, so when Mr. Black opened both of them only, there were two more closed door in the left exit and one closed door in the right exit. So Mr. Black wasn't able to exit at that moment. When he opened the third door, all doors from the right exit became open, so Mr. Black was able to exit the house. In the second example when the first two doors were opened, there was open closed door in each of the exit. With three doors opened Mr. Black was able to use the left exit.

Input

题意翻译

## 题目描述 三年过去了,伦敦仍在下雨,布莱克先生不得不关上家里的所有门,以免被水淹没。然而,有一次天晴了,布莱克先生打开了一扇又一扇的门,直到他打开了家里所有的门。 布莱克先生家里正好有两个出口,我们把它们分别命名为左出口和右出口。每个出口都有几个门,所以布莱克先生家里的每个门要么位于左边,要么位于右边。你知道每个门的位置。最初所有的门都是关闭的。布莱克先生只有在至少一个出口的所有门都打开的情况下才能离开房子。请按照布莱克先生开门的顺序,找出最小的索引k,以便布莱克先生能在打开第一个k门后离开房子。 注意到布莱克先生最多每扇门开一次,最后所有的门都开了。 ## 输入: 第一行包含整数n(2≤n≤200000)门的数量。 下一行包含n个整数:布莱克先生开门的顺序。如果第i个打开的门位于左出口,则这些整数的第i个等于0;如果它位于右出口,则等于1。 保证左出口至少有一扇门,右出口至少有一扇门。 ## 输出: 最小的整数k,这样在布莱克先生打开第一个k门后,他就可以离开房子了。 ## 说明: ### 第一个例子: 前两个门是从左出口开的,所以当布莱克先生只打开了两个门时,左出口还有两个关闭的门,右出口有一个关闭的门。所以布莱克先生当时不能离开。 当他打开第三扇门时,右出口的所有门都打开了,所以布莱克先生可以离开房子。 ### 第二个例子: 当前两个门被打开时,每个出口都有一个打开、关闭的门。 布莱克先生开了三扇门,就可以从左边的出口出去了

加入题单

上一题 下一题 算法标签: