Problem — https://cses.fi/problemset/task/1163 13

I am not getting this problem. I think the sample output is incorrect!

Input: 8 3 3 6 2

Output: 5 3 3

According to the sample, the input answer should be: 5 3 2 but the sample output is 5 3 3

Demonstration:

0 1 2 3 4 5 6 7 8 ! ! ! I mean after adding 2 how the longest path without traffic light is 3 and not 2? Somebody, please help. Is there a catch that I am losing?

`6-3=3`

So the longest passage is 3, not 2.But we have put a tower on 6 so why we are also taking 6 in answer, my point is that on 4 and 5 there will not be any tower but on 6 there will be a tower and on 3 also there will be tower too

Sorry, I didn't understand it. Initially we have:

After adding first traffic lights at point

`3`

:Here we have the longest passage without traffic lights with length 5:

`3-8`

. Next we add the traffic lights at point`6`

:Now we have two longest passages with length 3:

`0-3`

and`3-6`

. And finally we add the traffic lights at the point`2`

:The longest passage among all possible passages (

`0-2`

,`2-3`

,`3-6`

,`6-8`

) is`3-6`

with the length`3`

. So the last answer is`3`

.Got it at last. The problem is about the

distancefree of the traffic lights, not about the consecutive number of points free of the traffic lights and of maximum length. We can freely drive from the point`3`

to the point`6`

without meeting a single traffic lights.Okk, got it, thanks