Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) — initializes the data structure with the given length.
• void set(int index, int val) — sets the element at the given index to val.
• int snap() — takes a snapshot and returns the snap_id (increments by 1 each call).
• int get(int index, int snap_id) — returns the value at index at the time of the given snapshot.

Example:

SnapshotArray(3), set(0,5), snap()→0, set(0,6), get(0,0)→5