三年过去了,一切都没有改变。伦敦还在下雨,布莱克先生不得不关上家里所有的门,以免被水淹。然而,有一次,布莱克先生变得非常紧张,他打开一扇门,然后打开另一扇门,然后再打开一扇门,直到他打开了家里所有的门。
布莱克先生的房子正好有两个出口,我们将它们命名为左出口和右出口。每个出口都有几扇门,因此布莱克先生家的每扇门要么位于左侧出口,要么位于右侧出口。您知道每扇门的位置。最初所有的门都是关闭的。当且仅当至少一个出口的所有门都打开时,布莱克先生才能离开房子。给你一个 Black 先生打开门的顺序,请找到最小的索引 $$$k$$$,以便 Black 先生在打开第一个 $$$k$$$ 门后可以离开房子。
我们要注意的是,布莱克先生每扇门最多打开一次,最后所有的门都打开了。
输入
第一行包含整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — 门的数量。
下一行包含 $$$n$$$ 整数:布莱克先生开门的顺序。如果第 $$$i$$$ 个打开的门位于左侧出口,则这些整数中的第 $$$i$$$ 等于 $$$0$$$;如果它位于右侧出口,则这些整数中的第 $$$1$$$ 等于 $$$1$$$。
保证至少有一扇门位于左侧出口,并且至少有一扇门位于右侧出口。
输出
打印最小的整数 $$$k$$$,以便 Black 先生打开第一扇 $$$k$$$ 门后,他能够离开房子。
示例
输入 #1
5 0 0 1 0 0
输出 #1
3
输入 #2
4 1 0 0 1
输出 #2
3
注意
在第一个示例中,前两扇门来自左侧出口,因此当布莱克先生仅打开这两扇门时,左侧出口中还有两扇关闭的门,右侧出口中还有一扇关闭的门。所以布莱克先生此时无法退出。
当他打开第三扇门时,右侧出口的所有门都打开了,因此布莱克先生能够离开房子。
在第二个示例中,当前两扇门打开时,每个出口都有打开的关闭的门。
当三扇门打开时,布莱克先生能够使用左侧出口。