1129. Get Maximum in Generated Array

An array nums of length n+1 is generated by: nums[0]=0, nums[1]=1, nums[2i]=nums[i], and nums[2i+1]=nums[i]+nums[i+1] for valid i. Given n, return the maximum value in nums. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the maximum generated value.

Examples

Input: {"n":7}
Output: 3
Explanation: The generated array peaks at 3.

Input: {"n":2}
Output: 1
Explanation: Maximum is 1.

Input: {"n":0}
Output: 0
Explanation: Only zero.

Constraints

• 0<=n<=100

Asked by