410078: GYM103938 F Bat-shoe Toss

Freetail Hackers is an organization focused on bringing students who are passionate about technology together to build cool tech, learn new skills, and become involved in the hackathon and tech communities. We put on HackTX, an annual hackathon that brings students from all over the country to build new technology. Learn more about Freetail Hackers

For their field day event, Freetail Hackers has decided to play one of their favorite bat-related games, Bat-shoes. Bat-shoes is played similarly to Horseshoes, but with multiple pegs and some special rules.

There are $$$N$$$ pegs in a row and $$$N$$$ people on a team facing the pegs. The goal of the game is to toss bat-shoes onto the pegs, where each person tosses bat-shoes onto the peg directly in front of them.

Each person starts out with a different number of bat-shoes, given by $$$a_1,...,a_N$$$. Players then toss in the order given (i.e. $$$1...N$$$). Players can score extra points by forming an increasing sequence – that is, if player $$$i$$$ tosses $$$x_i$$$ bat-shoes onto their peg, then player $$$i+1$$$ tosses $$$x_{i+1} > x_i$$$ bat-shoes onto their peg, player $$$i+2$$$ tosses $$$x_{i+2} > x_{i+1}$$$ bat-shoes onto their peg, and so on ($$$0 < x_i \le a_i$$$ for all $$$i$$$).

Your team wants to know: what's the maximum length increasing sequence your team can create, if you play optimally?

The first line contains one integer $$$N$$$ ($$$1 \le N \le 10^6$$$), the number of pegs and the number of people on your team.

The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^6$$$), representing the number of batshoes the players start out with.

Output an integer representing the maximum length increasing sequence your team can create if everyone plays optimally.

6
2 5 6 2 7 9

4

In the example, your team can create an increasing sequence of length 4 if player 3 tosses 1 batshoe onto their peg, player 4 tosses 2 batshoes, player 5 tosses 7 batshoes, and player 6 tosses 9 batshoes ($$$1 < 2 < 7 < 9$$$). It can be shown that this is the maximum length increasing sequence you can obtain.