TopCoder

User's AC Ratio

97.2% (35/36)

Submission's AC Ratio

67.3% (68/101)

Tags

Description

先前李老闆參加了東南亞五日三夜______遊,在抵達一個貧窮的村落時,看到了村莊內的小孩們長期缺乏營養、醫療、教育的情況之後,決定改造這個村莊,提供營養的食物、建立醫療設施、教育機構等。

首先為了能夠順利運送物資,大老闆們決定在這個地方建立鐵路運輸系統。車站及鐵路的樣子如下圖:

車廂的以$1$到$N$來編號,一開始所有的車廂都在A方向,以$1$到$N$的順序排好,編號越小的在越前面(靠近中間車站(station)的方向)。

現在需要把這些物資運往B方向,但唯一的運送方法只能藉由中間的車站來運輸,車站類似一個堆疊結構,先進入車站的車廂必須等後進入的車廂都離開車站後才能離開車站。車廂都是可以獨立移動的,一旦一個車廂往車站移動後就不能返回A方向;往B方向移動之後也不能再回到車站。車站的空間很大,可以容納所有車廂。

工人們希望車廂能夠以特定的方式排列在B方向上,以方便作業。你的任務是寫一個程式,檢測這個鐵路系統是否能使得全部的車廂以一特定的順序排列在B方向的鐵軌上。

Input Format

輸入的第一行是一個正整數$T ( 1 \leq T \leq 10)$,代表共有幾組測試資料。每組測試資料的第一行是一個數$N( 1 \leq N \leq 10^5)$,代表車廂的數量。接著第二行有$N$個整數,內容為$1, 2, \cdots , N$的任意排列,為工人們所希望的排列方式。

Output Format

對每一組測試資料,輸出該$1, 2, \cdots , N$的任意排列是否可能。如果可能,請輸出Yes,若不可能則輸出No。

Sample Input 1

4
5
1 2 3 4 5
5
5 4 3 2 1
5
5 4 1 2 3
7
4 5 3 7 6 2 1

Sample Output 1

Yes
Yes
No
Yes

Hints

和平真好。

Problem Source

UVa
NEOJ Problem 19

Subtasks

No. Testdata Range Constraints Score
1 0~5 $N \leq 10$ 60
2 6~7 $N \leq 1000$ 20
3 8~9 $N \leq 100000$ 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 3
9 1000 65536 65536 3