10 3 1 1 1 2 1 1 2 1 1 1 1 2 2 2 1 1 2 3 3 4 4 2 2 2 1 1 2 2 3 3 4 2 2 2 1 1 2 3 2 2 3 2 2 2 1 1 2 3 2 4 2 2 1 1 1 2 1 9 1 2 2 2 5 2 8 5 2 5 5 5 8 8 2 8 5 8 8 3 2 1 1 1 2 2 1 3 1 1 3 3 3 2 2 200000 100001 100002 200000 900000 200000 200000 900000