F - Useless for LIS Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

長さ N の整数列 A が与えられます。

t = 1, 2, \dots ,N について、 A_t が A の最長増加部分列に含まれることがあるか判定してください。

A_t が A の最長増加部分列に含まれることがあるとは、以下のことをいいます。

  • 最長増加部分列の長さを L とする。各要素が 1 以上 N 以下の単調増加な整数列 i = (i_1, i_2, \dots ,i_L) \ (i_1 < i_2 < \dots < i_L) であって以下をすべて満たすものが存在する。

    • A_{i_1} < A_{i_2} < \dots < A_{i_L}
    • ある k \ (1 \leq k \leq L) が存在して i_k = t である

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

最長増加部分列とは？

列 A の部分列とは A の要素をいくつか抜き出して元の順に並べてできる列を指します。

列 A の最長増加部分列とは、 A の狭義単調増加な部分列のうち列の長さが最大のものを指します。

制約

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで \mathrm{case_i} は i 番目のケースの入力を意味する。各ケースは以下の形式で与えられる。

N
A_1 A_2 \cdots A_N

出力

以下の形式で出力せよ。

\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T

ここで \mathrm{answer}_i は i 番目のケースの出力を意味する。各ケースについては、次の通りである。

A_t が A の最長増加部分列に含まれることがある t が m 個存在し、昇順に i_1, i_2, \dots ,i_m であったとする。このとき、以下の形式で出力せよ。

m
i_1 i_2 \cdots i_m

入力例 1

1
5
2 1 4 5 3

出力例 1

4
1 2 3 4

最長増加部分列の 1 つは (2, 4, 5) で、長さは 3 です。(1, 4, 5) も最長増加部分列の 1 つです。しかし、 A_5 を含む最長増加部分列はありません。

よって、 1, 2, 3, 4 を出力します。

入力例 2

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

出力例 2

5
1 3 4 5 6
2
4 5

Score : 525 points

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