Score : $525$ points

问题陈述

给定一个长度为 $N$ 的整数序列 $A$。

对于每个 $t = 1, 2, \dots, N$，确定 $A_t$ 是否包含在 $A$ 的最长递增子序列中。

这里，$A_t$ 包含在 $A$ 的最长递增子序列中当且仅当满足以下条件：

• 设 $L$ 为 $A$ 的最长递增子序列的长度。存在一个严格递增的整数序列 $i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L)$，其中每个元素都在 $1$ 和 $N$ 之间（包括 $1$ 和 $N$），满足以下所有条件：

  • $A_{i_1} < A_{i_2} < \dots < A_{i_L}$。
  • 对于某个 $k \ (1 \leq k \leq L)$，有 $i_k = t$。

你将得到 $T$ 个测试用例；解决每一个。

什么是最长递增子序列？

一个序列 $A$ 的子序列是通过从 $A$ 中提取一些元素而不改变顺序得到的序列。

一个序列 $A$ 的最长递增子序列是严格递增且长度最大的子序列。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given an integer sequence $A$ of length $N$.

For each $t = 1, 2, \dots, N$, determine whether $A_t$ is included in a longest increasing subsequence of $A$.

Here, $A_t$ is included in a longest increasing subsequence of $A$ if and only if the following holds:

• Let $L$ be the length of a longest increasing subsequence of $A$. There exists a strictly increasing integer sequence $i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L)$, where each element is between $1$ and $N$, inclusive, that satisfies all of the following conditions:

  • $A_{i_1} < A_{i_2} < \dots < A_{i_L}$.
  • $i_k = t$ for some $k \ (1 \leq k \leq L)$.

You are given $T$ test cases; solve each of them.

What is a longest increasing subsequence?

A subsequence of a sequence $A$ is a sequence that can be derived by extracting some elements from $A$ without changing the order.

A longest increasing subsequence of a sequence $A$ is a subsequence of $A$ that is strictly increasing with the greatest possible length.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ across all test cases is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

Here, $\mathrm{case_i}$ represents the input for the $i$-th case. Each case is given in the following format:

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answers in the following format:

$\mathrm{answer}_1$

$\mathrm{answer}_2$

$\vdots$

$\mathrm{answer}_T$

Here, $\mathrm{answer}_i$ represents the output for the $i$-th case. For each case, let there be $m$ indices $t$ such that $A_t$ is included in a longest increasing subsequence of $A$, which are $i_1, i_2, \dots, i_m$ in ascending order. Print these in the following format:

$m$

$i_1$ $i_2$ $\cdots$ $i_m$

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is $(2, 4, 5)$, with a length of $3$. Another longest increasing subsequence is $(1, 4, 5)$. However, no longest increasing subsequence includes $A_5$.

Therefore, print $1, 2, 3, 4$.

Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5