An ugly number is a positive integer whose only prime factors are 2, 3, or 5. By convention, 1 is also ugly. Given n, return the n-th ugly number (1-indexed).
Input
n: the 1-indexed position in the ugly number sequence
Output
The n-th ugly number.
Examples
Example 1
Inputn = 10
Output12
Explanation: The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.
Example 2
Inputn = 4
Output4
Constraints
1 <= n <= 1690
Maintain three pointers into the sequence multiplied by 2, 3, and 5 to generate the next ugly number in O(n) time.