Sachverhalt:
A.
A._, geboren 1969, bezog seit 1. Januar 2007 eine ganze Rente der Invalidenversicherung (IV-Grad: 100 %; Verfügung vom 12. September 2008). Nach einer ersten Rentenrevision, die keine erhebliche Änderung ergeben hatte (Mitteilung vom 2. November 2011), leitete die IV-Stelle des Kantons Zug im August 2012 ein weiteres Revisionsverfahren ein. Unter Berücksichtigung der Ergebnisse von im Juni sowie im Juli/August 2013 durchgeführten Observationen sistierte die IV-Stelle mit Verfügung vom 20. Juni 2014 die Rente und veranlasste in der Folge insbesondere eine Begutachtung bei Dr. med. B._, Facharzt Psychiatrie und Psychotherapie FMH, Rehaklinik C._, vom 8. Mai 2015. Nach Stellungnahme des Regionalen Ärztlichen Dienstes und durchgeführtem Vorbescheidverfahren verfügte die IV-Stelle am 8. Oktober 2015 die Einstellung der Invalidenrente.
B.
Eine daraufhin von A._ erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zug, Sozialversicherungsrechtliche Kammer, mit Entscheid vom 14. April 2016 ab (Ziff. 1 Dispositiv).
C.
A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragt die Aufhebung von Ziff. 1 Dispositiv des vorinstanzlichen Entscheides und die Rückweisung der Sache an die Vorinstanz zur ergänzenden Abklärung, eventualiter die ununterbrochene und fortdauernde Ausrichtung der bisherigen Invalidenrente. In prozessualer Hinsicht ersucht sie um Gewährung der unentgeltlichen Prozessführung und Verbeiständung.

Erwägungen:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
2.
Streitig ist, ob das kantonale Gericht den Gehörsanspruch der Beschwerdeführerin verletzt hat.
2.1. Die Vorinstanz erwog, die Beschwerdegegnerin habe zu Recht gestützt auf das Gutachten des Dr. med. B._ festgestellt, dass derzeit eine psychiatrische Diagnose mit Auswirkungen auf die Arbeitsfähigkeit nicht überwiegend wahrscheinlich zu beweisen sei. Von einem verbesserten Gesundheitszustand könne daher nicht gesprochen werden. Indes wirke sich im Rahmen von <ref-law> die entsprechende Beweislosigkeit zu Lasten der Beschwerdegegnerin aus, weshalb diese grundsätzlich die bisherige Rente weiter zu gewähren hätte. In der Folge prüfte das kantonale Gericht, ob die Rentenaufhebung mit der substituierten Begründung der prozessualen Revision (<ref-law>) zu schützen sei und bejahte dies.
2.2. Die Beschwerdeführerin rügt, das kantonale Gericht habe die Rentenaufhebung mit einer neuen, substituierten Begründung geschützt, ohne ihr die Parteirechte zu gewähren. Die IV-Stelle habe die Rente wegen eines angeblich verbesserten Gesundheitszustandes gestützt auf <ref-law> aufgehoben. Im kantonalen Beschwerdeverfahren habe es daher für sie keinen Anlass gegeben, auf eine prozessuale Revision (<ref-law>) einzugehen. Indem die Vorinstanz ihr keine Gelegenheit zur Stellungnahme eingeräumt habe, sei <ref-law> unheilbar verletzt worden. Ohnehin fehle es an einem Revisionsgrund und schliesslich wäre ein solcher auch nicht rechtzeitig geltend gemacht worden.
3.
Soweit die Vorinstanz die auf <ref-law> gestützte Rentenaufhebungsverfügung vom 8. Oktober 2015 mit der substituierten Begründung der prozessualen Revision (<ref-law>) geschützt hat, ist dieses Vorgehen, gestützt auf den Grundsatz der Rechtsanwendung von Amtes wegen (<ref-law>), nicht zu beanstanden. Die Versicherte rügt aber zu Recht, dass das kantonale Gericht ihr vorgängig Gelegenheit zur Stellungnahme hätte einräumen müssen (Urteil 9C_272/2009 vom 16. September 2009 E. 4.1, in: SVR 2010 IV Nr. 19 S. 58). Dies rechtfertigt sich deshalb, weil die Grundlagen für eine Revision im Sinne von <ref-law> (Anpassung an erheblich geänderte tatsächliche Verhältnisse) nicht identisch sind mit jenen für eine prozessuale Revision wegen vorbestandener neuer Tatsachen und Beweismittel, deren Beibringung zuvor nicht möglich war (<ref-law>). Indem es dies unterliess, hat es den Anspruch der Beschwerdeführerin auf rechtliches Gehör in der Tat verletzt. Gegen eine Heilung im bundesgerichtlichen Verfahren sprechen, wie die Beschwerdeführerin zu Recht geltend macht, die eingeschränkte Kognition des Bundesgerichtes in Bezug auf den vorinstanzlich festgestellten Sachverhalt (<ref-law> sowie Art. 105 Abs. 1 und 2 BGG) sowie der grundsätzliche Anspruch auf Einhaltung des Instanzenzuges (Urteil 8C_1027/2009 vom 17. August 2010 E. 2.2 mit Hinweisen, in: SZS 2010 S. 514). Der angefochtene Entscheid ist somit, ohne dass auf die übrigen Rügen der Beschwerdeführerin einzugehen wäre, aufzuheben und die Sache ist an das kantonale Gericht zur Gewährung des rechtlichen Gehörs und zu neuem Entscheid zurückzuweisen.
4.
Die im Sinne von <ref-law> offensichtlich begründete Beschwerde ist im vereinfachten Verfahren ohne Durchführung eines Schriftenwechsels gutzuheissen.
5.
Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>) und der Beschwerdeführerin eine Parteientschädigung zu bezahlen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Zug, Sozialversicherungsrechtliche Kammer, vom 14. April 2016, wird aufgehoben. Die Sache wird zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Rechtsvertreter der Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Zug, Sozialversicherungsrechtliche Kammer, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 12. Juli 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Bollinger Hammerle