题解

题目描述

小红在二维平面上让蛇从最内层开始以“只能右转”的方式行走，构成一个单螺旋。具体地，蛇依次向右（东）、下（南）、左（西）、上（北）……重复四个方向，每次直行的步数依次为

。问在行走过程中蛇是否会与自己先前经过的身体部分相交（即“撞到自己”）。若会相交，输出 Yes，否则输出 NO。

思路概述

题目内容

刚学完 $c$ 语言的小红，开发了贪吃蛇 $1.0$ 版本，在这个贪吃蛇中，蛇只能向右转弯。即蛇的行进方式呈单螺旋结构(如图)：

小红记录了从内向外蛇的每一节长度，即每次直走 $a_i$ 的长度，随后右转 $90$ 度。小红希望你判断蛇是否会撞到自己的身体。

输入描述

第一行输入测试用例的个数 $T$ 。

对于每一组测试用例第一行输入蛇的节数 $N$ 。

随后一行给出 $N$ 个正整数 $x_i$ ，表示每一节的长度。

$1≤T<10$

$1≤N≤ 10^5$

$1≤x_i≤10^9$

输出描述

对于每一组测试用例单独输出一行字符串。

若蛇能撞到自身，输出"$Yes$"，否则输出"$NO$"

补充说明

所谓的单螺旋结构：类似于如图所示：

但是:图二所示的情况不满足题意(因此图二是一个双螺旋)：

样例1

输入

1
6
5 7 11 12 16 17

输出

NO

样例2

输入

1
6
2 3 4 4 7 7

输出

NO