Go to Stensele. If DoT was used, then take the portal out. On the world map, follow the sand and narrow rivers moving diagonally NW. Eastern Arch is located about 25 squares this way with a few extra tiles westward. If you hit nothing but water, you've gone too far north and not enough west.
At floor 15, the Ninjas Guild can be found. You can keep going past this for more RD floors.