暂无测试数据。

题目描述

有一个长条状的棋盘,长度为n。一开始在某些位置上会有一个棋子。现在你可以进行操作,在一次操作中,你可以选择一个棋子,然后找到其左边或者右边的第一个空格子,并把棋子放在对应的空格子上。特别地,如果所选的棋子左边没有空格子则无法令其向左移动,右边的情况类似。

现在给你一个棋盘的初始局面,问是否可以在10步及以内变成给定的另外一个局面。如果可行,则输出最小步数,否则输出QAQ。

输入格式

输入第1行1个正整数n。

输入第2行n个数0或者1,0即没有棋子,1即有棋子,表示初始局面。

输入第3行n个数0或者1,意义同上,表示给定的最后局面。

输出格式

输出仅一行一个数字表示最小步数，或者QAQ表示没有在10步及以内的可行方案。

输入输出样例

输入 #1复制

10
1 0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 1 1 1 1
输出 #1复制
6

说明/提示

对于25%的数据,n<=5。

对于50%的数据,n<=10。

对于60%的数据,n<=12。

对于80%的数据,n<=16。

对于100%的数据,n<=20。