Using array and fit to curve changes orientation of object
If I'm not mistaking, Blender uses the world's Y axis as reference to align your object to the curve. Something like that.
So theoretically, you would only need to rotate your object at a 90° angle (or -90°) on the world's Z axis. Maybe also apply the object's rotation via CtrlA.
Nice demo picture by the way!