{"problem":{"name":"Planar Tree","description":{"content":"There are $N$ vertices on a circumference. The vertices are numbered $1$ to $N$ in clockwise order, and Vertex $i$ has an integer $A_i$ written on it, where $A_i$ is $1$, $2$, $3$, or $4$. Here, $A$ c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc058_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ vertices on a circumference. The vertices are numbered $1$ to $N$ in clockwise order, and Vertex $i$ has an integer $A_i$ written on it, where $A_i$ is $1$, $2$, $3$, or $4$. Here, $A$ contains each of $1$, $2$, $3$, and $4$ at least once.\nConsider making a tree by adding $N-1$ edges connecting these $N$ vertices. Here, the following conditions must be satisfied.\n\n*   If Vertices $x$ and $y$ are directly connected by an edge, $|A_x-A_y|=1$.\n    \n*   When the edges are drawn as segments, no two of them intersect except at an endpoint.\n    \n\nFor instance, the figure below shows a tree that satisfies the conditions:\n![image](https://img.atcoder.jp/agc058/8ed6a07d693053455f589dff2d9dccfa.png)\nDetermine whether it is possible to construct a tree that satisfies the conditions.\nSolve $T$ test cases for each input file.\n\n## Constraints\n\n*   $1 \\leq T \\leq 75000$\n*   $4 \\leq N \\leq 300000$\n*   $1 \\leq A_i \\leq 4$\n*   $A$ contains each of $1$, $2$, $3$, and $4$ at least once.\n*   The sum of $N$ in one input file does not exceed $300000$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc058_c","tags":[],"sample_group":[["3\n4\n1 2 3 4\n4\n1 3 4 2\n4\n1 4 2 3","Yes\nYes\nNo"],["3\n8\n4 2 3 4 1 2 2 1\n8\n3 2 2 3 1 3 3 4\n8\n2 3 3 2 1 4 1 4","Yes\nYes\nNo\n\nThe first test case corresponds to the figure in the Problem Statement."]],"created_at":"2026-03-03 11:01:14"}}