Temperature LIS Boost

This is an Agentics migration of Frontier-CS algorithmic problem 229.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Farmer John has found historical data from $n$ consecutive days. The temperature on the $i$-th day was $t_i$. He decides to make an analysis of historical temperatures and find a subsequence of days (not necessarily consecutive) where the temperature is strictly increasing.

Formally, FJ is interested in finding the length of the longest increasing subsequence (LIS) of $(t_1, t_2, \dots , t_n)$, that is, the largest possible $k$ for which it is possible to choose an increasing sequence of indices $1 \leq a_1 < a_2 < \dots < a_k \leq n$ such that $t_{a_1} < t_{a_2} < . . . < t_{a_k}$.

FJ wants to find a really long subsequence and that is why he decided to cheat a bit. In one operation, he can choose a non-empty interval of days and an integer $d$ $(-x \leq d \leq x)$ and he will increase the temperature in each of those days by $d$. It is allowed to choose $d = 0$. What is the largest possible length of the LIS after 10 such operations?

Input Format

• The first line of the input contains two space-separated integers $n$ and $x$ $(1 \leq n \leq 200000, 0 \leq x \leq 10^9)$, the number of days and the limit for the absolute value of $d$.
• The second line contains $n$ integers $t_1, t_2, \dots , t_n$ $(1 \leq t_i \leq 10^9 )$ separated by spaces, the sequence of historical temperatures.

Output Format

• The output should contain 11 lines
• The first line should contain the largest possible length of the LIS after 10 changes
• For each of the next lines, $i$-th line should contain three integers $l$, $r$, $d$ $(1 \leq l \leq r \leq n, -x \leq d \leq x)$, the interval of days and the change in temperature.

Scoring

• Assume the longest LIS you find after 10 changes is $len$. Your score will be $\frac{len}{n}$ if your output is valid, otherwise 0.