A number triangle is built like Pascal's triangle, but each entry sums **three** neighbors from the row above instead of two.
Row 1 is a single 1. To get row r (for r > 1) from row r - 1: row r has two more entries than row r - 1, sticking out by one extra position on each side. Line up row r's middle entry with row r - 1's middle entry; then every entry of row r equals the sum of the entry diagonally above-left, the entry directly above, and the entry diagonally above-right in row r - 1 — treating any of those three positions that fall outside row r - 1 as 0.
So row 1 is [1], row 2 is [1, 1, 1], row 3 is [1, 2, 3, 2, 1], row 4 is [1, 3, 6, 7, 6, 3, 1], and so on — row r always has 2r - 1 entries.
Given a row number n (1-indexed), return the **1-indexed position from the left** of the first even value in row n. If row n has no even value at all, return -1.
Example cases
- row 3in n = 3out 2Row 3 is [1, 2, 3, 2, 1]; the first even value, 2, sits at 1-indexed position 2.
- row 4in n = 4out 3Row 4 is [1, 3, 6, 7, 6, 3, 1]; the first even value, 6, sits at 1-indexed position 3.
- row 1 has no even valuein n = 1out -1Row 1 is just [1] — no even value exists, so the answer is -1.
Constraints
- 1 <= n <= 10^9
- Row values grow combinatorially, so building the actual row is only feasible for small n.
3