問題一覧 > 通常問題

No.1369 交換門松列・竹

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : maimai / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
5 ProblemId : 3422 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-29 22:12:47

定義

3つの要素から成る数列 $v = (a_1,a_2,a_3)$ が次の条件を満たす時、$v$ は門松列であると言い伝えられています。

  1. $a_1,a_2,a_3$ は全て異なる
  2. 3つの要素のうち $a_2$ が最も大きい、あるいは最も小さい

さらに、$n$ 個の要素(ただし $3\le n$ )から成る数列 $w = (a_1,...,a_n)$ が
どの連続した3つの要素を取り出しても門松列であるとき $w$は門松列列であると言います。

問題文

$N$ 要素から成る数列が与えられます。
残念ながら、この数列は門松列列ではないことが保証されています。

あなたは、ちょうど1回任意の2要素を選択し、交換します。同じ値の2要素を選択することは出来ません。 全く交換しないことも許されません。

上記の操作後、数列を門松列列に出来るか判定してください。

入力

1つの入力に $T$ 個のテストケースが含まれます。

1行目にテストケースの個数 $T$ が与えられ、 続く2行ごとに、各テストケースが与えられます。

$T$
$N_1$
$A_{1,1}\ \ldots\ A_{1,N_1}$
$\ldots$
$N_T$
$A_{T,1}\ \ldots\ A_{T,N_T}$

$1 \le T \le 10^4$
$3 \le N_j \le 5\times 10^4$
$1\le A_{j, i} \le N$
$\sum_{j\in 1\ldots T}N_j \le 5\times 10^4$

入力に含まれる値はすべて整数である。
それぞれの $j$ 番目のテストケースにおいて、 $A_{j,1},\ldots,A_{j,{N_j}}$ は門松列列では無い。

出力

各テストケースについて、可能なら Yes 、不能なら No を改行区切りで出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
3
1 2 3
9
1 2 3 4 5 6 7 8 9
8
1 4 2 3 4 2 3 1
9
1 4 2 3 5 8 6 7 1
出力
Yes
No
No
Yes

1 2 3は、 1と2を交換すると、2 1 3となり、数列を門松列列に出来ます。

1 2 3 4 5 6 7 8 9は、1回の交換では門松列列にできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。