Cây Chiều Cao Nhỏ Nhất

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$ là thứ tự duyệt BFS của một cây có gốc tại đỉnh $1$. Cụ thể, thuật toán BFS được mô tả bằng đoạn giả mã sau:

a = []          # thứ tự các đỉnh được xử lý
q = Queue()
q.put(1)        # đặt gốc vào hàng đợi
while q không rỗng:
    k = q.pop()
    a.append(k)
    for y in g[k]:   # g[k] là danh sách con của k, đã sắp xếp tăng dần
        q.put(y)

Lưu ý rằng đối với mỗi đỉnh, các con của nó được duyệt theo thứ tự tăng dần giá trị nhãn.

Có thể có nhiều cây cùng cho ra dãy duyệt BFS $a$. Hãy tìm chiều cao nhỏ nhất trong tất cả các cây như vậy.

Chiều cao của cây là độ sâu lớn nhất của một đỉnh, trong đó độ sâu của đỉnh là số cạnh trên đường đi từ gốc tới đỉnh đó (gốc có độ sâu $0$).

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ là thứ tự duyệt BFS.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là chiều cao nhỏ nhất có thể.

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le 2·{10}^5$
• $1\le a_i\le n$, các $a_i$ phân biệt, $a_1=1$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ