I don't know. But the length of best sequence $$$a$$$ is at least $$$85$$$, because $$$\operatorname{lcm}(1,2,\dots,42) \lt 10^{18}$$$.

It's hard to determine whether a sequence is valid, so I restrict the elements in $$$a$$$ to be powers of prime numbers.

Even though I added the condition, I can't find the best one that satisfies the condition.

I used DFS with pruning(may cause missing the best one) to find a good one.

I guess your solution is to connect $$$(x\bmod i,i)$$$ for all $$$1\le i \lt n$$$. (The nodes are 0-indexed).

With some modifications to the solution, it can be achieved for $$$n=101$$$, and the correctness is guaranteed.

Instead of connecting $$$(x\bmod i,i)$$$, we can connect $$$(x\bmod a_i,i)$$$.

0, 1, 2, 3, 4, 5, 5, 7, 7, 8, 9, 9, 11, 11, 11, 13, 13, 13, 16, 17, 17, 17, 19, 19, 19, 23, 23, 23, 23, 25, 25, 27, 29, 29, 29, 29, 31, 31, 31, 31, 32, 37, 37, 37, 37, 41, 41, 41, 41, 43, 43, 43, 43, 47, 47, 47, 47, 49, 49, 53, 53, 53, 53, 59, 59, 59, 59, 61, 61, 61, 61, 64, 67, 67, 67, 67, 71, 71, 71, 71, 73, 73, 73, 73, 79, 79, 79, 79, 81, 83, 83, 83, 83, 89, 89, 89, 89, 97, 97, 97, 97

Proof:

We need to prove that after deleting at most $$$49$$$ elements of $$$a$$$, the $$$\operatorname{lcm}$$$ of $$$a$$$ is still greater than $$$10^{18}$$$.

The sequence $$$a$$$ only contains powers of prime numbers. Therefore, different prime numbers can be considered independent.

For a prime $$$p$$$, let $$$p^k$$$ be the greatest power of $$$p$$$ that occurred in the sequence $$$a$$$, it is optimal for the grader to delete all $$$p^k$$$ first, then delete all $$$p^{k-1}$$$, ..., until $$$p$$$.

We can use dynamic programming to calculate the maximum possible decrease of the $$$\operatorname{lcm}$$$ caused by the grader.