{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\u003c!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01 Transitional//EN\"\u003e\u003chtml\u003e\u003chead\u003e\u003cMETA http-equiv\u003d\"Content-Type\" content\u003d\"text/html; charset\u003dutf-8\" /\u003e\u003c/head\u003e\u003cbody\u003e\u003c/body\u003e\u003c/html\u003e\u003c/!doctype\u003e\u003c/p\u003e\n\u003cdiv\u003e\n\u003cp\u003e\n Our well known coding mafia went to the city. \u003ci\u003eFarzi Coder\u003c/i\u003e is the boss here. He hired a new member named \u003ci\u003eLambu Keyboard\u003c/i\u003e in his gang. \u003ci\u003eFarzi Coder\u003c/i\u003e is so smart (at least that\u0027s what he thinks), so he wants to test \u003ci\u003eLambu Keyboard\u0027s\u003c/i\u003e programming skills. He gave him this task:\n \u003c/p\u003e\n\n\u003cp\u003e There are n buildings (numbered from left to right) with heights H\u003csub\u003e1\u003c/sub\u003e, H\u003csub\u003e2\u003c/sub\u003e...H\u003csub\u003en\u003c/sub\u003e. You can start jumping from any building.\u003c/p\u003e\n\u003cp\u003e\n The rules of jumping are:\n \u003c/p\u003e\n\u003col\u003e\n\u003cli\u003e You can only jump to a building with lesser height than the height of the current building. \u003c/li\u003e\n\u003cli\u003e In first turn you can jump either way, and 2\u003csup\u003end\u003c/sup\u003e jump will be in the opposite direction of previous jump and must end in between current index and previous index, i.e if we start jumping from building 5, initially we can jump in either direction. Let\u0027s say we jump to building 8, then in next jump we can only jump in left direction and only on buildings with indices 6, 7. Let\u0027s say we jump to building 6, then next time we can only jump in right direction and between 6 and 8 i.e to 7. \u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e We need to find the maximum number of jumps he can make, considering every building as the starting point.\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003e First line contains an integer \u003cb\u003en\u003c/b\u003e i.e. the number of buildings.\u003cbr /\u003e\u003cbr /\u003e\n Second line contains n space separated integers denoting heights of buildings from 1 to n.\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003e One line containing n integers, the i\u003csup\u003eth\u003c/sup\u003e integer will denote the maximum possible number of jumps starting from i\u003csup\u003eth\u003c/sup\u003e building.\u003c/p\u003e\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ n ≤ 5000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ H\u003csub\u003e1\u003c/sub\u003e, H\u003csub\u003e2\u003c/sub\u003e ... H\u003csub\u003en\u003c/sub\u003e ≤ 10000\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch2\u003eSample\u003c/h2\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cpre\u003e5\n1 3 4 2 5\n \u003c/pre\u003e\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cpre\u003e0 1 1 1 2\n \u003c/pre\u003e\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e If starting building is with height 1 then you can\u0027t jump to any other building.\u003cbr /\u003e\u003cbr /\u003e\n If starting building is with height 3 then you can jump either to building with height 2 on right or with height 1 on left. But there will be at most one jump.\u003cbr /\u003e\u003cbr /\u003e\n If starting building is with height 5 then one possible optimal sequence is to jump to building with height 3 then to building with height 2. So maximum number of jumps is 2.\u003cbr /\u003e \u003c/p\u003e\n\u003c/div\u003e\n\u003cp\u003e\u003c/p\u003e\n"}}]}