1231. Beautiful Arrangement — Count Permutations

Given an array nums of distinct positive integers, a permutation of nums is beautiful if for every 1-indexed position i the value placed there is divisible by i or divides i. Return the number of beautiful permutations. (With nums = [1, 2, ..., n] this is the classic Beautiful Arrangement count.) The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the number of beautiful permutations.

Examples

Input: {"nums":[1,2]}
Output: 2
Explanation: Both orders are beautiful.

Input: {"nums":[1,2,3]}
Output: 3
Explanation: Three beautiful permutations.

Input: {"nums":[1]}
Output: 1
Explanation: Single element.

Constraints

• 1<=n<=15
• distinct positive integers

Asked by